Submission #471023

# Submission time Handle Problem Language Result Execution time Memory
471023 2021-09-06T16:57:07 Z AmirElarbi Cake (CEOI14_cake) C++14
0 / 100
2000 ms 10304 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){
    //cout << id << " " << ns << " " << ne << endl;
    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;
    } else {
        s[ns] += lazy[id];
        //cout << ns << " " << s[ns] << endl;
    }
    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){
    unlazy(v,i,j);
    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);
    //cout << i << " " << j << endl;
    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;
    }
    //cout << x << " " << y << endl;
    int md = (i+j)/2;
    updr(v*2,i,md, x, y);
    updr(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;
            }
            //for(auto x : s)
                //cout << x << " ";
            //cout << 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);
            //for(auto x : s)
               // cout << x << " ";
            //cout << endl;
        }
    }
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 928 KB Time limit exceeded
2 Incorrect 1285 ms 940 KB Output isn't correct
3 Execution timed out 2060 ms 844 KB Time limit exceeded
4 Correct 298 ms 716 KB Output is correct
5 Execution timed out 2073 ms 1580 KB Time limit exceeded
6 Execution timed out 2075 ms 1484 KB Time limit exceeded
7 Execution timed out 2076 ms 1484 KB Time limit exceeded
8 Correct 316 ms 972 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 405 ms 5552 KB Output isn't correct
2 Incorrect 243 ms 5216 KB Output isn't correct
3 Incorrect 234 ms 5064 KB Output isn't correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 527 ms 10300 KB Output isn't correct
6 Incorrect 442 ms 10304 KB Output isn't correct
7 Incorrect 255 ms 6076 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 1040 ms 580 KB Output isn't correct
2 Incorrect 1729 ms 956 KB Output isn't correct
3 Execution timed out 2082 ms 2724 KB Time limit exceeded
4 Execution timed out 2091 ms 2984 KB Time limit exceeded
5 Execution timed out 2092 ms 752 KB Time limit exceeded
6 Execution timed out 2068 ms 2916 KB Time limit exceeded
7 Execution timed out 2073 ms 1348 KB Time limit exceeded
8 Execution timed out 2074 ms 5076 KB Time limit exceeded
9 Execution timed out 2073 ms 9536 KB Time limit exceeded
10 Execution timed out 2054 ms 852 KB Time limit exceeded
11 Execution timed out 2073 ms 1836 KB Time limit exceeded
12 Execution timed out 2076 ms 9452 KB Time limit exceeded
13 Execution timed out 2045 ms 9908 KB Time limit exceeded