Submission #116993

#	Time	Username	Problem	Language	Result	Execution time	Memory
116993		JohnTitor	Cake (CEOI14_cake)	C++11	35 / 100	2084 ms	25464 KiB

cake

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Cake"
int n, a;
int d[250001];
vector <int> highest;
class segment_tree{
public:
    using pointer=segment_tree*;
    pointer left, right;
    int l, r, m;
    int b;
    segment_tree(int l, int r){
        this->l=l;
        this->r=r;
        m=(l+r)/2;
        if(l==r) b=l;
        else{
            left=new segment_tree(l, m);
            right=new segment_tree(m+1, r);
            if(d[left->b]>d[right->b]) b=left->b;
            else b=right->b;
        }
    }
    int get_max(int u, int v){
        if(l>v||r<u) return 0;
        if(u<=l&&v>=r) return d[b];
        else return max(left->get_max(u, v), right->get_max(u, v));
    }
    int find_last_from_left(int maxd){
        if(l==r) return (d[l]<=maxd)?l:(l-1);
        if(d[left->b]>maxd) return left->find_last_from_left(maxd);
        else return right->find_last_from_left(maxd);
    }
    int find_last_from_right(int maxd){
        if(l==r) return (d[r]<=maxd)?r:(r+1);
        if(d[right->b]>maxd) return right->find_last_from_right(maxd);
        else return left->find_last_from_right(maxd);
    }
    void update(int u){
        if(l==r) return;
        else{
            if(m>=u) left->update(u);
            else right->update(u);
            if(d[left->b]>d[right->b]) b=left->b;
            else b=right->b;
        }
    }
};
segment_tree::pointer tl, tr;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(a);
    FOR(i, 1, n){
        read(d[i]);
        if(d[i]>n-10) highest.pb(i);
    }
    sort(highest.begin(), highest.end(), [](int a, int b){
        return d[a]>d[b];
    });
    if(a!=1&&a!=n){
        tl=new segment_tree(1, a-1);
        tr=new segment_tree(a+1, n);
    }
    {
        int q;
        char c;
        int i, e;
        read(q);
        while(q--){
            while(!isalpha(c=getchar()));
            if(c=='F'){
                read(i);
                if(i==a) writeln(0);
                else if(a==1||a==n) writeln(abs(a-i));
                else if(i>a) writeln(i-tl->find_last_from_right(tr->get_max(a+1, i)));
                else writeln(tr->find_last_from_left(tl->get_max(i, a-1))-i);
            }
            else{
                read(i);
                read(e);
                if(a==1||a==n) continue;
                for(auto &x: highest) if(x==i){
                    swap(x, highest.back());
                    highest.pop_back();
                    break;
                }
                highest.pb(i);
                FFOR(j, 1, e) d[highest[j-1]]++;
                d[i]=d[highest[e-1]]+1;
                sort(highest.begin(), highest.end(), [](int a, int b){
                    return d[a]>d[b];
                });
                if(i>a) tr->update(i);
                if(i<a) tl->update(i);
//                FOR(i, 1, n) cerr<<d[i]<<" \n"[i==n];
            }
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50