oj.uz

답안 #471022

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471022 2021-09-06T16:38:48 Z AmirElarbi 케이크 (CEOI14_cake) C++14
0 / 100
 933 ms 11884 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define fi first
#define se second
#define INF 1e7
#define unsigned u
#define eps 1e-18
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 100005;
vi s;int n;
ii tree[1000000];int lazy[1000000], flag[1000000];
void unlazy(int id, int ns, int ne){
    if(!flag[id])
        return;
    tree[id].fi += lazy[id]*(ne-ns+1);
    tree[id].se += lazy[id]*(ne-ns+1);
    if(ns!=ne){
        int l = 2*id;
        int r = l+1;
        lazy[l] += lazy[id];
        lazy[r] += lazy[id];
        flag[l] = flag[r] = 1;
    }
    flag[id] = 0;
    lazy[id] = 0;
}
ii mrg(ii a, ii b)
{
    return {min(a.fi, b.fi), max(a.se,b.se)};
}
void build(int v = 1, int i = 0, int j = n-1){
    if(i == j){
       tree[v] = {s[i],s[i]};
       return;
    }
    int md = (i+j)/2;
    build(v*2, i, md);
    build(v*2+1, md+1, j);  
    tree[v] = mrg(tree[v*2],tree[v*2+1]);
}
ii query(int v, int i, int j, int x , int y){
    unlazy(v, i, j);
    if(j < x || i > y)
        return {INF, 0};
    if(i >= x && j <= y){
        return tree[v]; 
    }
    int md = (i+j)/2;
    ii a = query(v*2, i, md, x, y), b = query(v*2+1, md+1, j, x, y);
    return mrg(a,b);
}
int get_first(int v, int lv, int rv, int l, int r, int x, bool k) {
    unlazy(v, lv, rv);
    if(lv > r || rv < l) return -1;
    if(l <= lv && rv <= r) {
        if(tree[v].se <= x) return -1;
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(k){
                if(tree[2*v].se  > x) {
                    v = 2*v;
                    rv = mid;
                }else {
                    v = 2*v+1;
                    lv = mid+1;
                }
            } else {
                if(tree[2*v+1].se > x) {
                    v = 2*v+1;
                    lv = mid+1;
                }else {
                    v = 2*v;
                    rv = mid;
                }
            }
        }
        return lv;
    }
    int mid = lv + (rv-lv)/2;
    if(k){
        int rs = get_first(2*v, lv, mid, l, r, x,k);
        if(rs != -1) return rs;
        return get_first(2*v+1, mid+1, rv, l ,r, x,k);
    } else {
        int rs = get_first(2*v+1, mid+1, rv, l ,r, x,k);
        if(rs != -1) return rs;
        return get_first(2*v, lv, mid, l, r, x,k);
    }
}

void upd(int v, int i, int j, int pos, int value){
    if(j < pos || i > pos)
        return;
    if(i == j){
       tree[v] = {value,value};
       s[pos] = value;
       return;
    }
    int md = (i+j)/2;
    upd(v*2, i, md, pos, value);
    upd(v*2+1, md+1, j, pos, value);
    tree[v] = mrg(tree[v*2],tree[v*2+1]);
} 
void updr(int v, int i, int j, int x, int y){
    unlazy(v, i, j);
    if(tree[v].se < x || tree[v].fi > y)
        return;
    if(tree[v].fi >= x && tree[v].se <= y){
        lazy[v]--;
        flag[v] = 1;
        unlazy(v, i, j);
        return;
    }
    int md = (i+j)/2;
    upd(v*2,i,md, x, y);
    upd(v*2+1,md+1,j, x, y);
    tree[v] = mrg(tree[v*2], tree[v*2+1]);
}
int main() { 
    optimise;
    int start;
    cin >> n >> start;
    start--;
    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        s.pb(a);
    }
    build();
    int q;
    cin >> q;
    while(q--){
        char be;
        cin >> be;
        if(be == 'F'){
            int a;
            cin >> a;
            a--;
            if(start > a){
                int mx = query(1,0,n-1,a,start-1).se;
                int lim = get_first(1,0,n-1,start+1, n-1,mx,1);
                if(lim == -1) lim = n;
                cout << lim - a -1 << endl;
            } else if(a == start){
                cout << 0 << endl;
            } else {
                int mx = query(1,0,n-1,start+1,a).se;
                int lim = get_first(1,0,n-1,0,start-1,mx,0);
                cout << a - lim - 1  << endl;
            }
        } else {
            int a,b;
            cin >> a >> b;
            a--;
            b = n-b+1;
            updr(1,0,n-1,s[a]+1,b);
            upd(1,0,n-1,a,b);
        }
    }
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 252 ms 3868 KB Output isn't correct
2 Incorrect 202 ms 3620 KB Output isn't correct
3 Incorrect 233 ms 3912 KB Output isn't correct
4 Incorrect 193 ms 2592 KB Output isn't correct
5 Incorrect 291 ms 5028 KB Output isn't correct
6 Incorrect 278 ms 5288 KB Output isn't correct
7 Incorrect 259 ms 5028 KB Output isn't correct
8 Incorrect 208 ms 4652 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 271 ms 3376 KB Output isn't correct
2 Incorrect 235 ms 3336 KB Output isn't correct
3 Incorrect 228 ms 3400 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 279 ms 6188 KB Output isn't correct
6 Incorrect 290 ms 6224 KB Output isn't correct
7 Incorrect 252 ms 6152 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 468 KB Output isn't correct
2 Incorrect 71 ms 536 KB Output isn't correct
3 Incorrect 127 ms 2132 KB Output isn't correct
4 Incorrect 125 ms 1992 KB Output isn't correct
5 Incorrect 191 ms 648 KB Output isn't correct
6 Incorrect 259 ms 3268 KB Output isn't correct
7 Incorrect 276 ms 1868 KB Output isn't correct
8 Incorrect 132 ms 4548 KB Output isn't correct
9 Incorrect 933 ms 11884 KB Output isn't correct
10 Incorrect 635 ms 2584 KB Output isn't correct
11 Incorrect 756 ms 6216 KB Output isn't correct
12 Incorrect 902 ms 11464 KB Output isn't correct
13 Incorrect 877 ms 11732 KB Output isn't correct