oj.uz

답안 #257765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257765 2020-08-04T18:04:16 Z doowey 케이크 (CEOI14_cake) C++14
35 / 100
 2000 ms 5368 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 * 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 ask(int node, int cl, int cr, int tl, int tr){
    if(cr < tl)
        return 0;
    if(cl > tr)
        return 0;
    if(cl >= tl && cr <= tr)
        return tree[node];
    int mid = (cl + cr) / 2;
    return max(ask(node * 2, cl, mid, tl, tr), ask(node * 2 + 1, mid + 1, cr, tl, tr));
}

int getrng(int node, int cl, int cr, int tl, int tr, int mode, int vlx){
    if(tl > tr || tree[node] < vlx)
        return -1;
    if(cr < tl)
        return -1;
    if(cl > tr)
        return -1;
    if(cl >= tl && cr <= tr){
        if(cl==cr){
            if(tree[node] < vlx) return -1;
            return cl;
        }
        if(mode == 0){ // to left
            int mid = (cl + cr) / 2;
            if(tree[node * 2] > vlx)
                return getrng(node * 2, cl, mid, tl, tr, mode, vlx);
            if(tree[node * 2 + 1] > vlx)
                return getrng(node * 2 + 1, mid + 1, cr, tl, tr,mode, vlx);
            return -1;
        }
        else{
            int mid = (cl + cr) / 2;
            if(tree[node * 2 + 1] > vlx){
                return getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
            }
            if(tree[node * 2] > vlx)
                return getrng(node * 2, cl, mid, tl, tr, mode, vlx);
            return -1;
        }
    }
    int mid = (cl + cr) / 2;
    int f1,f2;
    if(mode == 0){
        f1 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
        f2 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
    }
    else{
        f2 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
        f1 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
    }
    if(f1 != -1) return f1;
    return f2;
}


int main(){
    fastIO;
    int n, st;
    cin >> n >> st;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        upd(1, 1, n, 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(1, 1, n, st + 1, nx);
                ly = getrng(1,1,n,1,st-1,1,mx);
                if(ly == -1) ly = 0;
                res += st - ly - 1;
            }
            else if(nx < st){
                res += st - nx;
                mx = ask(1, 1, n,nx, st - 1);
                ly = getrng(1,1,n,st+1,n,0,mx);
                if(ly == -1) ly = n + 1;
                res += ly - st - 1;
            }
            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;
                    upd(1, 1, n, nx, pp);
                    niw.push_back(nx);
                }
                sz = niw.size();
                pp = nw - sz;
                upd(1, 1, n, cc[p], pp);
                niw.push_back(cc[p]);
            }
            cc = niw;
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 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 163 ms 384 KB Output is correct
5 Correct 1497 ms 888 KB Output is correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2087 ms 1016 KB Time limit exceeded
2 Execution timed out 2077 ms 1148 KB Time limit exceeded
3 Execution timed out 2089 ms 1016 KB Time limit exceeded
4 Correct 513 ms 1912 KB Output is correct
5 Execution timed out 2084 ms 1156 KB Time limit exceeded
6 Execution timed out 2096 ms 1272 KB Time limit exceeded
7 Execution timed out 2084 ms 1300 KB Time limit exceeded
8 Correct 631 ms 2388 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 3704 KB Output is correct
2 Correct 84 ms 3576 KB Output is correct
3 Correct 78 ms 3576 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 125 ms 5368 KB Output is correct
6 Correct 131 ms 5340 KB Output is correct
7 Correct 112 ms 5112 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2072 ms 996 KB Time limit exceeded
2 Execution timed out 2080 ms 1196 KB Time limit exceeded
3 Execution timed out 2096 ms 1656 KB Time limit exceeded
4 Execution timed out 2085 ms 2040 KB Time limit exceeded
5 Execution timed out 2086 ms 1080 KB Time limit exceeded
6 Execution timed out 2063 ms 2180 KB Time limit exceeded
7 Execution timed out 2088 ms 1184 KB Time limit exceeded
8 Execution timed out 2071 ms 2840 KB Time limit exceeded
9 Execution timed out 2040 ms 4984 KB Time limit exceeded
10 Execution timed out 2073 ms 1092 KB Time limit exceeded
11 Execution timed out 2067 ms 1396 KB Time limit exceeded
12 Execution timed out 2068 ms 4980 KB Time limit exceeded
13 Execution timed out 2097 ms 4856 KB Time limit exceeded