CSES - Putka Open 2015 – finaali - Results
Submission details
Task:Kyselyt
Sender:
Submission time:2015-12-20 17:11:02 +0200
Language:C++
Status:READY
Result:88
Feedback
groupverdictscore
#10
#2ACCEPTED25
#3ACCEPTED63
Test results
testverdicttimegroup
#10.19 s1details
#20.19 s1details
#30.19 s1details
#40.19 s1details
#50.18 s1details
#6ACCEPTED0.08 s2details
#7ACCEPTED0.10 s2details
#8ACCEPTED0.08 s2details
#9ACCEPTED0.08 s2details
#10ACCEPTED0.09 s2details
#11ACCEPTED0.21 s3details
#12ACCEPTED0.19 s3details
#13ACCEPTED0.21 s3details
#14ACCEPTED0.17 s3details
#15ACCEPTED0.21 s3details

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
#define N (2<<16)
using namespace std;
long v[2*N];
long m[2*N];
void c (int k, long a) {
k += N;
v[k] = a;
//cout<<"foo: "<<k<<endl;
m[k] = a;
for (k /= 2; k > 0; k /= 2) {
v[k] = v[2*k] + v[2*k+1];
m[k] = min(m[2*k], v[2*k+1]);
}
}
void qu (long a, long b) {
a += N;
b += N;
long w = (b - a + 1);
long s = 0;
long mn = 100000;
while (a <= b) {
if (a % 2 == 1) {
mn = min(mn, m[a]);
s += v[a++];
}
if (b % 2 == 0) {
mn = min(mn, m[b]);
s += v[b--];
}
a /= 2;
b /= 2;
}
s -= (mn - 1) * w;
//cout<<s<<" "<<(w * (w + 1) / 2)<<endl;
if (s == (w * (w + 1) / 2)) cout<<"10-4"<<endl;
else cout<<"QAQ"<<endl;
}
int main () {
int n, q;
cin>>n>>q;
if (n > 1000 || q > 1000) {
for (int i = 0; i < n; i++) {
int k;
cin>>k;
c(i + 1, k);
}
for (int i = 0; i < q; i++) {
char x;
cin>>x;
int a, b;
cin>>a>>b;
//a--; b--;
if (x == '!') {
long l = v[a + N];
//cout<<l<<" "<<(a + N)<<":"<<v[b + N]<<" "<<(b + N)<<endl;
c(a, v[b + N]);
c(b, l);
} else {
qu(a, b);
}
}
} else {
int e[n];
for (int i = 0; i < n; i++) cin>>e[i];
for (int i = 0; i < q; i++) {
char c;
cin>>c;
int a, b;
cin>>a>>b;
set<int> s;
for (int x = a - 1; x < b; x++) {
s.insert(e[x]);
if (*s.end() - *s.begin() == b - a) cout<<"10-4"<<endl;
else cout<<"QAQ"<<endl;
}
}
}
}

Test details

Test 1

Group: 1

Verdict:

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

Test 2

Group: 1

Verdict:

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:

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

Test 4

Group: 1

Verdict:

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:

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

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