oj.uz

Submission #257754

# Submission time Handle Problem Language Result Execution time Memory
257754 2020-08-04T17:26:58 Z doowey Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 4088 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 250010;

int A[N];

int tree[N * 2 + 512];

int lim;
void setid(int x, int v){
    x += lim;
    tree[x] = v;
    x /= 2;
    while(x > 0){
        tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
        x /= 2;
    }
}

int ask(int l, int r){
    int ans = 0;
    l += lim;
    r += lim;
    while(l <= r){
        if(l % 2 == 1) ans = max(ans, tree[l ++ ]);
        if(r % 2 == 0) ans = max(ans, tree[r -- ]);
        l /= 2;
        r /= 2;
    }
    return ans;
}

int main(){
    fastIO;
    int n, st;
    cin >> n >> st;
    lim = n + 2;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        setid(i, A[i]);
    }
    vector<int> cc;
    for(int j = 0 ; j < 10 ; j ++ ){
        for(int i = 1; i <= n; i ++ ){
            if(n - j == A[i]){
                cc.push_back(i);
                break;
            }
        }
    }
    int q;
    cin >> q;
    int nx;
    int res;
    char typ;
    int mx;
    int ly;
    int li;
    int nw = n;
    int sz;
    int pp;
    vector<int> niw;
    for(int i = 1; i <= q; i ++ ){
        cin >> typ;
        if(typ == 'F'){
            cin >> nx;
            res = 1;
            if(nx > st){
                res += nx - st;
                mx = ask(st + 1, nx);
                ly = st;
                for(int lg = 19; lg >= 0; lg -- ){
                    li = ly - (1 << lg);
                    if(li <= 0) continue;
                    if(ask(li, st - 1) < mx){
                        ly = li;
                    }
                }
                res += st - ly;
            }
            else if(nx < st){
                res += st - nx;
                mx = ask(nx, st - 1);
                ly = st;
                for(int lg = 19; lg >= 0 ; lg -- ){
                    li = ly + (1 << lg);
                    if(li > n) continue;
                    if(ask(st + 1, li) < mx){
                        ly = li;
                    }
                }
                res += ly - st;
            }
            cout << res - 1 << "\n";
        }
        else{
            cin >> nx >> mx;
            mx -- ;
            if(cc[mx] == nx) continue;
            nw += 10;
            niw.clear();
            for(int p = 0 ; p < cc.size(); p ++ ){
                if(cc[p] == nx) continue;
                if(p == mx){
                    sz = niw.size();
                    pp = nw - sz;
                    setid(nx, pp);
                    niw.push_back(nx);
                }
                sz = niw.size();
                pp = nw - sz;
                setid(cc[p], pp);
                niw.push_back(cc[p]);
            }
            cc = niw;
        }
    }
    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:112:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int p = 0 ; p < cc.size(); p ++ ){
                             ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 42 ms 468 KB Output is correct
5 Correct 434 ms 760 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2087 ms 888 KB Time limit exceeded
2 Execution timed out 2084 ms 972 KB Time limit exceeded
3 Execution timed out 2077 ms 632 KB Time limit exceeded
4 Correct 266 ms 640 KB Output is correct
5 Execution timed out 2083 ms 972 KB Time limit exceeded
6 Execution timed out 2099 ms 888 KB Time limit exceeded
7 Execution timed out 2092 ms 988 KB Time limit exceeded
8 Correct 318 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2296 KB Output is correct
2 Correct 88 ms 2168 KB Output is correct
3 Correct 80 ms 2080 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 146 ms 4076 KB Output is correct
6 Correct 132 ms 4088 KB Output is correct
7 Correct 118 ms 3832 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 888 KB Time limit exceeded
2 Execution timed out 2085 ms 944 KB Time limit exceeded
3 Execution timed out 2074 ms 1528 KB Time limit exceeded
4 Execution timed out 2082 ms 1424 KB Time limit exceeded
5 Execution timed out 2072 ms 940 KB Time limit exceeded
6 Execution timed out 2087 ms 1572 KB Time limit exceeded
7 Execution timed out 2078 ms 1016 KB Time limit exceeded
8 Execution timed out 2084 ms 1912 KB Time limit exceeded
9 Execution timed out 2089 ms 3704 KB Time limit exceeded
10 Execution timed out 2072 ms 1004 KB Time limit exceeded
11 Execution timed out 2078 ms 1272 KB Time limit exceeded
12 Execution timed out 2086 ms 3320 KB Time limit exceeded
13 Execution timed out 2084 ms 3792 KB Time limit exceeded