제출 #1175855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175855		12345678	케이크 (CEOI14_cake)	C++20	0 / 100	363 ms	5976 KiB

cake

#include <bits/stdc++.h>

using namespace std;

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>n-10; i--) top.push_back(rid[i]);
    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; 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);
        }
        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';
            }
        }
    }

}

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