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