제출 #1144108

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

cake

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
struct node{
    int val,idx;
}arr[MAXN];
int ans[(MAXN<<2)][2],rk[MAXN],id[MAXN];
bool cmp(node a, node b){
    return a.val > b.val;
}
void build(int l, int r, int p, int t){
    if(l == r){
        ans[p][t] = arr[l].val;
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,p<<1,t); build(mid+1,r,(p<<1)|1,t);
    ans[p][t] = min(ans[p<<1][t],ans[(p<<1)|1][t]);
    //return ans[p][t];
}
void upd(int l, int r, int tar, int p, int t, int val){
    if(l == r){
        ans[p][t] = val;
        return;
    }
    int mid = (l+r)>>1;
    if(tar <= mid) upd(l,mid,tar,p<<1,t,val);
    else upd(mid+1,r,tar,(p<<1)|1,t,val);
    ans[p][t] = min(ans[p<<1][t],ans[(p<<1)|1][t]);
}
int query(int l, int r, int p, int tarl, int tarr, int t){
    if(tarl <= l && r <= tarr) return ans[p][t];
    int mid = (l+r)>>1, res = 1e9;
    if(tarl <= mid){
        res = min(res,query(l,mid,p<<1,tarl,tarr,t));
    }
    if(mid+1 <= tarr){
        res = min(res,query(mid+1,r,(p<<1)|1,tarl,tarr,t));
    }
    return res;
}
int findl(int l, int r, int p, int tar){
    if(ans[p][0] > tar) return l-1;
    if(l == r) return l;
    int mid = (l+r)>>1;
    if(ans[(p<<1)|1][0] < tar) return findl(mid+1,r,(p<<1)|1,tar);
    else return findl(l,mid,(p<<1),tar);
}
int findr(int l, int r, int p, int tar){
    if(ans[p][1] > tar) return r+1;
    if(l == r) return l;
    int mid = (l+r)>>1;
    if(ans[(p<<1)][1] < tar) return findr(l,mid,(p<<1),tar);
    else return findr(mid+1,r,(p<<1)|1,tar);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,A; cin >> N >> A;
    for(int i = 1;i<=N;++i){
        cin >> arr[i].val;
        arr[i].val = N-arr[i].val+1;
        arr[i].idx = i;
    }
    if(A != 1){
        build(1,A-1,1,0);
    }
    if(A != N){
        build(A+1,N,1,1);
    }
    sort(arr+1,arr+N+1,cmp);
    for(int i = 1;i<=N;++i){
        rk[i] = arr[i].idx;
        id[arr[i].idx] = i;
    }
    int Q; cin >> Q;
    int curmin = 1;
    while(Q--){
        char c; cin >> c;
        if(c == 'F'){
            int x; cin >> x;
            if(x == A) cout << "0\n";
			else if(x > A)
			{
				if(A == 1){cout << x-1 << "\n";continue;}
				//query(int l, int r, int p, int tarl, int tarr, int t)
				int Minn = query(A+1,N,1,A + 1 ,x , 1);
				int Pos = A - 1 - findl(1 , A-1 , 1 , Minn);
				cout << Pos + x - A << "\n";
			}
			else
			{
				if(A == N){cout << A-x << "\n";continue;}
				int Minn = query(1,A-1,1,x,A-1,0), Pos = findr(A+1,N,1,Minn)-A-1;
				cout << Pos + A - x << "\n";
			}
        }
        else{
            int x,y; cin >> x >> y; //x moves to y (y <= 10)
            int curp = min(N,10);
            for(int i = 1;i<=min(N,10);++i){ //move everything from 1 to curp up
                if(rk[i] == x){
                    curp = i;
                    break;
                }
            }
            for(int i = curp-1;i>=y;--i){ //legal because x must be freed
                rk[i+1] = rk[i];
            }
            rk[y] = x;
            for(int i = y;i>=1;--i){
                --curmin;
                if(rk[i] < A){
                    //upd(int l, int r, int tar, int p, int t, int val)
                    upd(1,A-1,rk[i],1,0,curmin);
                }
                else if(rk[i] > A){
                    upd(A+1,N,rk[i],1,1,curmin);
                }
            }
        }
    }
    return 0;
}

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