Submission #1175918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175918		12345678	Cake (CEOI14_cake)	C++20	100 / 100	350 ms	6048 KiB

cake

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int nx=3e5+5;

int n, a, h[nx], rid[nx], q, idx, e, t, b;
vector<int> top;
char opr;

struct segtree
{
    int mx[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return mx[i]=h[l], void();
        int md=(l+r)/2;
        build(l, md ,2*i);
        build(md+1, r, 2*i+1);
        mx[i]=max(mx[2*i], mx[2*i+1]);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return mx[i]=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        mx[i]=max(mx[2*i], mx[2*i+1]); 
    }
    int querymax(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return mx[i];
        int md=(l+r)/2;
        return max(querymax(l, md ,2*i, ql, qr), querymax(md+1, r, 2*i+1, ql, qr));
    }
    int getgreaterleft(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||mx[i]<=vl) return -1;
        if (l==r) return l;
        int md=(l+r)/2;
        int rvl=getgreaterleft(md+1, r, 2*i+1, idx, vl);
        return (rvl==-1)?getgreaterleft(l, md, 2*i, idx, vl):rvl;
    }
    int getgreaterright(int l, int r, int i, int idx, int vl)
    {
        if (r<idx||mx[i]<=vl) return -1;
        if (l==r) return l;
        int md=(l+r)/2;
        int lvl=getgreaterright(l, md, 2*i, idx, vl);
        return (lvl==-1)?getgreaterright(md+1, r, 2*i+1, idx, vl):lvl;
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>a;
    t=n;
    for (int i=1; i<=n; i++) cin>>h[i], rid[h[i]]=i;
    h[0]=h[n+1]=1e9;
    s.build(0, n+1, 1);
    for (int i=n; i>max(0, n-10); i--) top.push_back(rid[i]);
    //cout<<"before "<<top.size()<<'\n';
    cin>>q;
    while (q--)
    {
        cin>>opr;
        if (opr=='E')
        {
            cin>>idx>>e;
            int f=0;
            for (auto x:top) if (x==idx) f=1;
            vector<int> nw;
            if (!f) top.pop_back();
            else
            {
                vector<int> tmp;
                for (auto x:top) if (x!=idx) tmp.push_back(x);
                top=tmp;
            }
            for (int i=0; i<e-1; i++) nw.push_back(top[i]);
            nw.push_back(idx);
            for (int i=e-1; i<top.size(); i++) nw.push_back(top[i]);
            top=nw;
            for (int i=top.size()-1; i>=0; i--) s.update(0, n+1, 1, top[i], ++t);
            //cout<<"update "<<top.size()<<'\n';
        }
        else
        {
            cin>>b;
            if (a==b) cout<<"0\n";
            else if (a<b)
            {
                int tmp=s.querymax(0, n+1, 1, a+1, b);
                cout<<b-s.getgreaterleft(0, n+1, 1, a-1, tmp)-1<<'\n';
            }
            else
            {
                int tmp=s.querymax(0, n+1, 1, b, a-1);
                cout<<s.getgreaterright(0, n+1, 1, a+1, tmp)-b-1<<'\n';
            }
        }
    }
    //cout<<"after "<<top.size()<<'\n';
}

/*
5 2
5 2 3 1 4
13
E 2 3
F 2
F 5
F 1
E 3 3
E 4 3
E 4 2
E 4 1
F 3
E 2 4
E 5 2
E 2 1
F 4
*/

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