Task: | Kyselyt |
Sender: | |
Submission time: | 2015-12-20 14:15:23 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 25 |
#3 | ACCEPTED | 63 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.05 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.05 s | 1 | details |
#6 | ACCEPTED | 0.08 s | 2 | details |
#7 | ACCEPTED | 0.09 s | 2 | details |
#8 | ACCEPTED | 0.10 s | 2 | details |
#9 | ACCEPTED | 0.08 s | 2 | details |
#10 | ACCEPTED | 0.07 s | 2 | details |
#11 | ACCEPTED | 0.22 s | 3 | details |
#12 | ACCEPTED | 0.21 s | 3 | details |
#13 | ACCEPTED | 0.21 s | 3 | details |
#14 | ACCEPTED | 0.21 s | 3 | details |
#15 | ACCEPTED | 0.22 s | 3 | details |
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";elsecout << "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 ... |