oj.uz

Submission #257788

# Submission time Handle Problem Language Result Execution time Memory
257788 2020-08-04T19:27:54 Z doowey Cake (CEOI14_cake) C++14
100 / 100
 541 ms 9848 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 csh[10];
int nov[10];

int main(){
    fastIO;
    cin >> n >> start;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        setpos(i, A[i]);
        if(n - A[i] <= 9)
            csh[n - A[i]] = i;
    }
    for(int i = 1; i <= n; i ++ )
        if(csh[i] == 0) csh[i] = -1;
    int q;
    cin >> q;
    char typ;
    int qq;
    int res;
    int ff;
    int mx;
    int pp;
    int lim = n;
    int id;
    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(csh[qq] == pp) continue;
            lim += 10;
            id = 0;
            for(int y = 0; y < 10; y ++ ){
                if(csh[y] == -1) break;
                if(csh[y] == pp) continue;
                if(y == qq){
                    setpos(pp, lim - id);
                    nov[id++] = pp;
                }
                setpos(csh[y], lim - id);
                nov[id++] = csh[y];
            }
            for(int y = 0; y < 10; y ++ )
                if(csh[y] != -1)
                    csh[y] = nov[y];
        }
    }
    return 0;
}

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 4 ms 384 KB Output is correct
5 Correct 10 ms 640 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 4864 KB Output is correct
2 Correct 306 ms 4600 KB Output is correct
3 Correct 395 ms 4880 KB Output is correct
4 Correct 317 ms 1016 KB Output is correct
5 Correct 436 ms 5180 KB Output is correct
6 Correct 428 ms 5496 KB Output is correct
7 Correct 420 ms 5356 KB Output is correct
8 Correct 403 ms 972 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2680 KB Output is correct
2 Correct 64 ms 2552 KB Output is correct
3 Correct 58 ms 2424 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 102 ms 4476 KB Output is correct
6 Correct 109 ms 4476 KB Output is correct
7 Correct 87 ms 4216 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 792 KB Output is correct
2 Correct 41 ms 764 KB Output is correct
3 Correct 76 ms 2040 KB Output is correct
4 Correct 77 ms 1912 KB Output is correct
5 Correct 101 ms 1528 KB Output is correct
6 Correct 148 ms 3060 KB Output is correct
7 Correct 155 ms 2424 KB Output is correct
8 Correct 215 ms 3964 KB Output is correct
9 Correct 537 ms 9848 KB Output is correct
10 Correct 335 ms 4856 KB Output is correct
11 Correct 415 ms 6136 KB Output is correct
12 Correct 541 ms 9592 KB Output is correct
13 Correct 490 ms 9848 KB Output is correct