CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Kyselyt
Sender:Henrik Lievonen
Submission time:2015-12-20 14:28:25 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.14 s1details
#20.15 s1details
#30.14 s1details
#40.15 s1details
#50.14 s1details
#60.16 s2details
#70.16 s2details
#80.17 s2details
#90.16 s2details
#100.17 s2details
#110.16 s3details
#120.16 s3details
#130.18 s3details
#140.17 s3details
#150.16 s3details

Code

// C

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

template<typename T, int N, class CT, T inf>
class seqtree {
public:
  CT cmp;
  vector<T> tree;
  
  seqtree() : tree(2*N) {
    for (auto &v : tree)
      v = inf;
  }
  
  void set(int i, int v) {
    i += N;
    tree[i] = v;
    i /= 2;
    while (i > 0) {
      if (cmp(tree[2*i], tree[2*i+1]))
	tree[i] = tree[2*i];
      else
	tree[i] = tree[2*i+1];
      i /= 2;
    }
  }
  
  T get(int a, int b) {
    a += N;
    b += N;
    T r = inf;
    while (a < b) {
      if (a % 2 == 1) {
	if (cmp(tree[a], r))
	  r = tree[a];
	a++;
      }
      if (b % 2 == 0) {
	if (cmp(tree[b], r))
	  r = tree[b];
	b--;
      }
      a /= 2;
      b /= 2;
    }
    if (a == b) {
      if (cmp(tree[a], r))
	r = tree[a];
    }
    return r;
  }
};

const int max_size = 1<<4;
int main() {
  seqtree<int, max_size, less<int>, 1<<30> mintree;
  seqtree<int, max_size, greater<int>, -(1<<30)> maxtree;
  vector<int> vals(max_size);
  
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    vals[i] = a;
    mintree.set(i, a);
    maxtree.set(i, a);
  }
  
  for (int i = 0; i < q; i++) {
    char c;
    int a, b;
    cin >> c >> a >> b;
    if (c == '!') {
      swap(vals[a], vals[b]);
      mintree.set(a, vals[a]);
      mintree.set(b, vals[b]);
      maxtree.set(a, vals[a]);
      maxtree.set(b, vals[b]);
    } else {
      int m = mintree.get(a, b);
      int M = maxtree.get(a, b);
      if (M-m == b-a)
	cout<<"10-4\n";
      else
	cout<<"QAQ\n";
    }
  }
}

Test details

Test 1

Group: 1

Verdict:

input
1000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
QAQ
QAQ
10-4
QAQ
QAQ
...

Error:
*** Error in `input/code': munmap_chunk(): invalid pointer: 0x0000000001f35130 ***

Test 2

Group: 1

Verdict:

input
1000 1000
128 457 985 777 789 322 723 1 ...

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Error:
*** Error in `input/code': free(): invalid size: 0x0000000001f35130 ***

Test 3

Group: 1

Verdict:

input
1000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Error:
*** Error in `input/code': free(): invalid size: 0x0000000001a90130 ***

Test 4

Group: 1

Verdict:

input
1000 1000
642 565 22 258 295 380 339 341...

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Error:
*** Error in `input/code': munmap_chunk(): invalid pointer: 0x0000000000b30130 ***

Test 5

Group: 1

Verdict:

input
1000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
10-4
QAQ
QAQ
QAQ
QAQ
...

Error:
*** Error in `input/code': munmap_chunk(): invalid pointer: 0x0000000001841130 ***

Test 6

Group: 2

Verdict:

input
100000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
(empty)

Test 7

Group: 2

Verdict:

input
100000 1000
95033 30510 85695 94248 1652 9...

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
(empty)

Test 8

Group: 2

Verdict:

input
100000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
(empty)

Test 9

Group: 2

Verdict:

input
100000 1000
93701 32360 85873 85418 5145 3...

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
(empty)

Test 10

Group: 2

Verdict:

input
100000 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
QAQ
...

user output
(empty)

Test 11

Group: 3

Verdict:

input
100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
(empty)

Test 12

Group: 3

Verdict:

input
100000 100000
55896 749 62202 85583 19083 14...

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
(empty)

Test 13

Group: 3

Verdict:

input
100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
10-4
10-4
10-4
10-4
...

user output
(empty)

Test 14

Group: 3

Verdict:

input
100000 100000
96435 80769 7125 99626 45181 8...

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
(empty)

Test 15

Group: 3

Verdict:

input
100000 100000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
10-4
QAQ
QAQ
QAQ
10-4
...

user output
(empty)