oj.uz

Submission #257785

# Submission time Handle Problem Language Result Execution time Memory
257785 2020-08-04T19:21:43 Z doowey Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 4800 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;

struct Segt{
    int tree[N * 4 + 512];
    void upd(int node, int cl, int cr, int pos, int x){
        if(cl == cr){
            tree[node] = x;
            return ;
        }
        int mid = (cl + cr) / 2;
        if(mid >= pos)
            upd(node * 2, cl, mid, pos, x);
        else
            upd(node * 2 + 1, mid + 1, cr, pos, x);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }
    int get(int node, int cl, int cr, int tl, int tr){
        if(cr < tl || cl > tr)
            return 0;
        if(cl >= tl && cr <= tr){
            return tree[node];
        }
        int mid = (cl + cr) / 2;
        return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
    }
    int fin(int node, int cl, int cr, int vlx, int mode){
        if(tree[node] < vlx)
            return -1;
        if(cl == cr)
            return cl;
        int mid = (cl + cr) / 2;
        if(mode == 0){
            if(tree[node * 2 + 1] > vlx) return fin(node * 2 + 1, mid + 1, cr, vlx, mode);
            return fin(node * 2, cl, mid, vlx, mode);
        }
        else{
            if(tree[node * 2] > vlx) return fin(node * 2, cl, mid, vlx, mode);
            return fin(node * 2 + 1, mid + 1, cr, vlx, mode);
        }
    }
};

int start;
int n;

Segt Li, Ri;

void setpos(int id, int x){
    if(id < start){
        Li.upd(1, 1, n, id, x);
    }
    else if(id > start){
        Ri.upd(1, 1, n, id, x);
    }
}

int A[N];

int main(){
    fastIO;
    cin >> n >> start;
    vector<int> cc;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        setpos(i, A[i]);
    }
    for(int j = 0; j < 10; j ++ ){
        for(int x = 1 ; x <= n;  x ++ ){
            if(A[x] == n - j){
                cc.push_back(x);
                break;
            }
        }
    }
    int q;
    cin >> q;
    char typ;
    int qq;
    int res;
    int ff;
    int mx;
    int pp;
    int lim = n;
    for(int i = 1; i <= q; i ++ ){
        cin >> typ;
        if(typ == 'F'){
            cin >> qq;
            if(qq == start) cout << 0 << "\n";
            else{
                res = 1;
                if(qq > start){
                    res += qq - start;
                    mx = Ri.get(1, 1, n, start + 1, qq);
                    ff = Li.fin(1, 1, n, mx, 0);
                    if(ff == -1) ff = 0;
                    res += start - ff - 1;
                }
                else if(qq < start){
                    res += start - qq;
                    mx = Li.get(1, 1, n, qq, start - 1);
                    ff = Ri.fin(1, 1, n, mx, 1);
                    if(ff == -1) ff = n + 1;
                    res += ff - start - 1;
                }
                cout << res - 1 << "\n";
            }
        }
        else{
            cin >> pp >> qq;
            qq -- ;
            if(cc[qq] == pp) continue;
            lim += 10;
            vector<int> nw;
            for(int y = 0; y < cc.size(); y ++ ){
                if(cc[y] == pp) continue;
                if(y == qq){
                    setpos(pp, lim - (int)nw.size());
                    nw.push_back(pp);
                }
                setpos(cc[y], lim - (int)nw.size());
                nw.push_back(cc[y]);
            }
            cc = nw;
        }
    }
    return 0;
}

Compilation message

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

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 2 ms 384 KB Output is correct
4 Correct 74 ms 384 KB Output is correct
5 Correct 985 ms 1036 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 1024 KB Time limit exceeded
2 Execution timed out 2091 ms 1016 KB Time limit exceeded
3 Execution timed out 2097 ms 1016 KB Time limit exceeded
4 Correct 417 ms 1272 KB Output is correct
5 Execution timed out 2093 ms 1276 KB Time limit exceeded
6 Execution timed out 2096 ms 1144 KB Time limit exceeded
7 Execution timed out 2088 ms 1272 KB Time limit exceeded
8 Correct 509 ms 1512 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2680 KB Output is correct
2 Correct 63 ms 2552 KB Output is correct
3 Correct 58 ms 2552 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 101 ms 4800 KB Output is correct
6 Correct 103 ms 4728 KB Output is correct
7 Correct 89 ms 4472 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 924 KB Time limit exceeded
2 Execution timed out 2090 ms 1016 KB Time limit exceeded
3 Execution timed out 2076 ms 1604 KB Time limit exceeded
4 Execution timed out 2089 ms 1912 KB Time limit exceeded
5 Execution timed out 2096 ms 1016 KB Time limit exceeded
6 Execution timed out 2084 ms 1928 KB Time limit exceeded
7 Execution timed out 2079 ms 1168 KB Time limit exceeded
8 Execution timed out 2090 ms 2296 KB Time limit exceeded
9 Execution timed out 2085 ms 4476 KB Time limit exceeded
10 Execution timed out 2081 ms 1272 KB Time limit exceeded
11 Execution timed out 2055 ms 1328 KB Time limit exceeded
12 Execution timed out 2082 ms 4008 KB Time limit exceeded
13 Execution timed out 2091 ms 4216 KB Time limit exceeded