CSES - Putka Open 2015 – finaali

Submission details
Task:	Kyselyt
Sender:	Henrik Lievonen
Submission time:	2015-12-20 14:28:25 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	RUNTIME ERROR	0
#2	RUNTIME ERROR	0
#3	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	RUNTIME ERROR	0.14 s	1	details
#2	RUNTIME ERROR	0.15 s	1	details
#3	RUNTIME ERROR	0.14 s	1	details
#4	RUNTIME ERROR	0.15 s	1	details
#5	RUNTIME ERROR	0.14 s	1	details
#6	RUNTIME ERROR	0.16 s	2	details
#7	RUNTIME ERROR	0.16 s	2	details
#8	RUNTIME ERROR	0.17 s	2	details
#9	RUNTIME ERROR	0.16 s	2	details
#10	RUNTIME ERROR	0.17 s	2	details
#11	RUNTIME ERROR	0.16 s	3	details
#12	RUNTIME ERROR	0.16 s	3	details
#13	RUNTIME ERROR	0.18 s	3	details
#14	RUNTIME ERROR	0.17 s	3	details
#15	RUNTIME ERROR	0.16 s	3	details

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: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
`QAQ QAQ 10-4 QAQ QAQ ...` view save

Error:

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

Test 2

Group: 1

Verdict: RUNTIME ERROR

input
`1000 1000 128 457 985 777 789 322 723 1 ...` view save

correct output
`QAQ QAQ QAQ QAQ QAQ ...` view save

user output
`QAQ QAQ QAQ QAQ QAQ ...` view save

Error:

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

Test 3

Group: 1

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
`QAQ QAQ QAQ QAQ QAQ ...` view save

Error:

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

Test 4

Group: 1

Verdict: RUNTIME ERROR

input
`1000 1000 642 565 22 258 295 380 339 341...` view save

correct output
`QAQ QAQ QAQ QAQ QAQ ...` view save

user output
`QAQ QAQ QAQ QAQ QAQ ...` view save

Error:

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

Test 5

Group: 1

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
`10-4 QAQ QAQ QAQ QAQ ...` view save

Error:

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

Test 6

Group: 2

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
(empty)

Test 7

Group: 2

Verdict: RUNTIME ERROR

input
`100000 1000 95033 30510 85695 94248 1652 9...` view save

correct output
`QAQ QAQ QAQ QAQ QAQ ...` view save

user output
(empty)

Test 8

Group: 2

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
(empty)

Test 9

Group: 2

Verdict: RUNTIME ERROR

input
`100000 1000 93701 32360 85873 85418 5145 3...` view save

correct output
`QAQ QAQ QAQ QAQ QAQ ...` view save

user output
(empty)

Test 10

Group: 2

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 QAQ ...` view save

user output
(empty)

Test 11

Group: 3

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
(empty)

Test 12

Group: 3

Verdict: RUNTIME ERROR

input
`100000 100000 55896 749 62202 85583 19083 14...` view save

correct output
`QAQ QAQ QAQ QAQ QAQ ...` view save

user output
(empty)

Test 13

Group: 3

Verdict: RUNTIME ERROR

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

correct output
`10-4 10-4 10-4 10-4 10-4 ...` view save

user output
(empty)

Test 14

Group: 3

Verdict: RUNTIME ERROR

input
`100000 100000 96435 80769 7125 99626 45181 8...` view save

correct output
`QAQ QAQ QAQ QAQ QAQ ...` view save

user output
(empty)

Test 15

Group: 3

Verdict: RUNTIME ERROR

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

correct output
`10-4 QAQ QAQ QAQ 10-4 ...` view save

user output
(empty)

Putka Open 2015 – finaali

Kyselyt

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions (Henrik Lievonen)