oj.uz

Submission #257753

# Submission time Handle Problem Language Result Execution time Memory
257753 2020-08-04T17:24:55 Z doowey Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 6440 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;
            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:111:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int p = 0 ; p < cc.size(); p ++ ){
                             ~~^~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 1048 KB Time limit exceeded
2 Execution timed out 2080 ms 1300 KB Time limit exceeded
3 Execution timed out 2072 ms 1168 KB Time limit exceeded
4 Incorrect 189 ms 5112 KB Output isn't correct
5 Execution timed out 2094 ms 844 KB Time limit exceeded
6 Execution timed out 2093 ms 1020 KB Time limit exceeded
7 Execution timed out 2096 ms 1016 KB Time limit exceeded
8 Incorrect 228 ms 5368 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 3576 KB Output isn't correct
2 Incorrect 89 ms 3320 KB Output isn't correct
3 Incorrect 78 ms 3320 KB Output isn't correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 140 ms 6440 KB Output isn't correct
6 Incorrect 154 ms 6392 KB Output isn't correct
7 Incorrect 114 ms 6136 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 1152 KB Time limit exceeded
2 Execution timed out 2085 ms 912 KB Time limit exceeded
3 Execution timed out 2095 ms 1844 KB Time limit exceeded
4 Execution timed out 2094 ms 1912 KB Time limit exceeded
5 Execution timed out 2086 ms 1356 KB Time limit exceeded
6 Execution timed out 2073 ms 2176 KB Time limit exceeded
7 Execution timed out 2095 ms 1016 KB Time limit exceeded
8 Execution timed out 2091 ms 2564 KB Time limit exceeded
9 Execution timed out 2092 ms 5496 KB Time limit exceeded
10 Execution timed out 2091 ms 1528 KB Time limit exceeded
11 Execution timed out 2089 ms 1272 KB Time limit exceeded
12 Execution timed out 2088 ms 4720 KB Time limit exceeded
13 Execution timed out 2098 ms 5648 KB Time limit exceeded