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

Compiler report

input/code.cpp: In member function 'LL MinSegTree::set(LL, LL)':
input/code.cpp:34:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
input/code.cpp: In member function 'LL MaxSegTree::set(LL, LL)':
input/code.cpp:69:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
typedef long long LL;
using namespace std;
LL next_pow_2(LL n){
LL x = 1;
while(x < n) x *= 2;
return x;
}
class MinSegTree{
public:
vector<LL> v;
LL n;
MinSegTree(LL size){
n = next_pow_2(size);
v.resize(2*n,1e9);
}
LL set(LL index, LL value){
index += n;
v[index] = value;
index /= 2;
while(index != 0){
v[index] = min(v[index*2], v[index*2 + 1]);
index /= 2;
}
}
LL get(LL l, LL r){
LL ans = 1e9;
l += n;
r += n;
while(l <= r){
if(l % 2 == 1) ans = min(ans, v[l++]);
if(r % 2 == 0){
ans = min(ans, v[r--]);
}
l /= 2; r /= 2;
}
return ans;
}
};
class MaxSegTree{
public:
vector<LL> v;
LL n;
MaxSegTree(LL size){
n = next_pow_2(size);
v.resize(2*n,0);
}
LL set(LL index, LL value){
index += n;
v[index] = value;
index /= 2;
while(index != 0){
v[index] = max(v[index*2], v[index*2 + 1]);
index /= 2;
}
}
LL get(LL l, LL r){
LL ans = 0;
l += n;
r += n;
while(l <= r){
if(l % 2 == 1) ans = max(ans, v[l++]);
if(r % 2 == 0) ans = max(ans, v[r--]);
l /= 2; r /= 2;
}
return ans;
}
};
int main(){
LL n, q;
cin >> n >> q;
MinSegTree minTree(n);
MaxSegTree maxTree(n);
for(int i = 0; i < n; i++){
LL x; cin >> x;
minTree.set(i,x);
maxTree.set(i,x);
}
for(int i = 0; i < q; i++){
char type; cin >> type;
LL l,r; cin >> l >> r; l--; r--;
if(type == '!'){
LL lx = minTree.get(l,l);
LL rx = minTree.get(r,r);
minTree.set(l,rx);
minTree.set(r,lx);
maxTree.set(l,rx);
maxTree.set(r,lx);
} else{
if(maxTree.get(l,r) - minTree.get(l,r) == r-l)
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
...