Task: | Kyselyt |
Sender: | |
Submission time: | 2015-12-20 15:17:36 +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.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.06 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.06 s | 1 | details |
#6 | ACCEPTED | 0.07 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.08 s | 2 | details |
#11 | ACCEPTED | 0.21 s | 3 | details |
#12 | ACCEPTED | 0.21 s | 3 | details |
#13 | ACCEPTED | 0.21 s | 3 | details |
#14 | ACCEPTED | 0.20 s | 3 | details |
#15 | ACCEPTED | 0.20 s | 3 | details |
Code
#include<iostream>#include<vector>using namespace std;struct node {int64_t min,max;};int64_t M=1;void set(vector<node> &spuu, int64_t a, int64_t m) {a+=M;spuu[a].min=m;spuu[a].max=m;a/=2;while(a>=1) {spuu[a].min=min(spuu[2*a].min,spuu[2*a+1].min);spuu[a].max=max(spuu[2*a].max,spuu[2*a+1].max);a/=2;}}void get(vector<node> &spuu, int64_t a, int64_t b, int64_t &m, int64_t &Max) {a+=M;b+=M;while(a<=b) {m=min(spuu[a].min, m);m=min(spuu[b].min, m);Max=max(spuu[a].max, Max);Max=max(spuu[b].max, Max);a=(a+1)/2;b=(b-1)/2;}}int main(void) {int64_t n, q;cin >> n >> q;while(M<=2*n) M*=2;M/=2;vector<node> spuu(2*M);for(int64_t i=0;i<2*M;i++) {spuu[i].max=-1;spuu[i].min=(int64_t)100000000000;}for(int64_t i=0;i<n;i++) {int64_t a;cin >> a;set(spuu,i,a);}for(int64_t i=0;i<q;i++) {char c;int64_t a,b;cin >> c >> a >> b;a--;b--;if(c == '?') {int64_t min=1000000000000,max=-1;get(spuu, a, b, min, max);/*cout << "Max: " << max << " Min: " << min << endl;*/if(max-min==b-a) {cout << "10-4\n";} else {cout << "QAQ\n";}} else {int64_t tmp=spuu[M+a].max, rmp=spuu[M+b].max;set(spuu, a, rmp);set(spuu, b, tmp);/*for(int64_t i=0;i<spuu.size();i++) {cout << i << ": " << spuu[i].min << " " << spuu[i].max << endl;}*/}}}
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 ... |