Submission #676573

#	Time	Username	Problem	Language	Result	Execution time	Memory
676573		vjudge1	Cake (CEOI14_cake)	C++17	35 / 100	2099 ms	6748 KiB

cake

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl "\n"
const int mod = (int) 1e9+7;
const int N=2e5+5;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n,a; cin>>n>>a;
    int d[n+5],opd[n+5];
    for (int i=1;i<=n;i++) {
      cin>>d[i];
      opd[d[i]]=i;
    }

    int when[n+5];
    when[a]=0;
    int l=a-1,r=a+1,time=1;
    while (time<n) {
      if (l>=1  && ((r>n) || (r<=n && d[l]<d[r]))) {
        when[l]=time; time++; l--;
      }
      if (r<=n && ((l<1) || (l>=1 && d[r]<d[l]))) {
        when[r]=time; time++; r++;
      }
    }

    int q; cin>>q;
    while (q--) {
      char c; cin>>c;
      if (c=='F') {
        int x; cin>>x;
        cout<<when[x]<<endl;
      }
      else {
        int x,nw; cin>>x>>nw;
        nw=n-(nw-1);
        for (int i=d[x]+1;i<=nw;i++) {
          d[opd[i]]--; opd[d[opd[i]]]=opd[i];
        }
        d[x]=nw;
        opd[d[x]]=x;

        //for (int i=1;i<=n;i++) cout<<d[i]<<' '; cout<<endl;

        int l=a-1,r=a+1,time=1;
        while (time<n) {
          if (l>=1  && ((r>n) || (r<=n && d[l]<d[r]))) {
            when[l]=time; time++; l--;
          }
          if (r<=n && ((l<1) || (l>=1 && d[r]<d[l]))) {
            when[r]=time; time++; r++;
          }
        }
      }

    }

}

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