Submission #676575

#	Time	Username	Problem	Language	Result	Execution time	Memory
676575		vjudge1	Cake (CEOI14_cake)	C++17	35 / 100	2086 ms	22620 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++;
      }
    }

    vector<pair<int,pair<int,int> > >tst;

    int f=0,e=0;
    int q; cin>>q;
    while (q--) {
      char c; cin>>c;
      if (c=='F') {
        f++;
        int x; cin>>x;
        tst.push_back({1,{x,0}});
      }
      else {
        e++;
        int x,nw; cin>>x>>nw;
        tst.push_back({2,{x,nw}});
      }
    }

    int lste=-1;
    for (int qq=0;qq<tst.size();qq++) {
      int x=tst[qq].second.first;
      if (tst[qq].first==1) {
        if (e>100 && lste==-1) {
          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++;
            }
          }
        }
        cout<<when[x]<<endl;
        lste=1;
      }
      else {
        lste=-1;
        int nw=tst[qq].second.second;
        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;

        if (e<=100) {
          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++;
            }
          }
        }
      }

    }

}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:49:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int qq=0;qq<tst.size();qq++) {
      |                   ~~^~~~~~~~~~~

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