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

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