CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Kyselyt
Sender:Henrik Lievonen
Submission time:2015-12-20 14:29:01 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED25
#3ACCEPTED63
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.07 s1details
#6ACCEPTED0.08 s2details
#7ACCEPTED0.08 s2details
#8ACCEPTED0.08 s2details
#9ACCEPTED0.09 s2details
#10ACCEPTED0.08 s2details
#11ACCEPTED0.21 s3details
#12ACCEPTED0.21 s3details
#13ACCEPTED0.23 s3details
#14ACCEPTED0.22 s3details
#15ACCEPTED0.21 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<<17;
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: ACCEPTED

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
10-4
10-4
10-4
10-4
...

Test 2

Group: 1

Verdict: ACCEPTED

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
...

Test 3

Group: 1

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
...

Test 4

Group: 1

Verdict: ACCEPTED

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
...

Test 5

Group: 1

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
...

Test 6

Group: 2

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
10-4
...

Test 7

Group: 2

Verdict: ACCEPTED

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

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Test 8

Group: 2

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
10-4
...

Test 9

Group: 2

Verdict: ACCEPTED

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

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Test 10

Group: 2

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
QAQ
...

Test 11

Group: 3

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
10-4
...

Test 12

Group: 3

Verdict: ACCEPTED

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

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Test 13

Group: 3

Verdict: ACCEPTED

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
10-4
10-4
10-4
10-4
10-4
...

Test 14

Group: 3

Verdict: ACCEPTED

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

correct output
QAQ
QAQ
QAQ
QAQ
QAQ
...

user output
QAQ
QAQ
QAQ
QAQ
QAQ
...

Test 15

Group: 3

Verdict: ACCEPTED

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
10-4
QAQ
QAQ
QAQ
10-4
...