Submission #117204

#	Time	Username	Problem	Language	Result	Execution time	Memory
117204		IOrtroiii	Cake (CEOI14_cake)	C++14	100 / 100	848 ms	5872 KiB

cake

#include <bits/stdc++.h>

using namespace std;

const int N = 250250;

int n, start, q;
int a[N];
vector<int> top10;
bool intop[N];
int t[N << 2];

void build(int v, int l, int r) {
   if (l == r) {
      if (!intop[l]) {
         t[v] = a[l];
      }
      return;
   }
   int md = (l + r) >> 1;
   build(v << 1, l, md);
   build(v << 1 | 1, md + 1, r);
   t[v] = max(t[v << 1], t[v << 1 | 1]);
}

void upd(int v, int l, int r, int pos, int val) {
   if (pos > r || pos < l) return;
   if (l == r) {
      t[v] = val;
      return;
   }
   int md = (l + r) >> 1;
   upd(v << 1, l, md, pos, val);
   upd(v << 1 | 1, md + 1, r, pos, val);
   t[v] = max(t[v << 1], t[v << 1 | 1]);
}

int get(int v, int l, int r, int L, int R) {
   if (L > r || R < l) return 0;
   if (L <= l && r <= R) return t[v];
   int md = (l + r) >> 1;
   return max(get(v << 1, l, md, L, R), get(v << 1 | 1, md + 1, r, L, R));
}

int findL(int v, int l, int r, int pos, int val) {
   if (l > pos || t[v] < val) return 0;
   if (l == r) return l;
   int md = (l + r) >> 1;
   int ans = findL(v << 1 | 1, md + 1, r, pos, val);
   if (ans == 0) return ans = findL(v << 1, l, md, pos, val);
   return ans;
}

int findR(int v, int l, int r, int pos, int val) {
   if (r < pos || t[v] < val) return n + 1;
   if (l == r) return l;
   int md = (l + r) >> 1;
   int ans = findR(v << 1, l, md, pos, val);
   if (ans == n + 1) ans = findR(v << 1 | 1, md + 1, r, pos, val);
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n >> start;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      top10.push_back(i);
   }
   sort(top10.begin(), top10.end(), [&](int x, int y) {
      return a[x] > a[y];
   });
   while (top10.size() > 10) top10.pop_back();
   for (int v : top10) intop[v] = true;
   build(1, 1, n);
   cin >> q;
   while (q--) {
      char op;
      cin >> op;
      if (op == 'E') {
         int pos, rnk;
         cin >> pos >> rnk;
         --rnk;
         vector<int> ntop10;
         for (int i = 0; i < rnk; ++i) {
            ++a[top10[i]];
            ntop10.push_back(top10[i]);
         }
         a[pos] = a[top10[rnk]] + 1;
         if (!intop[pos]) {
            ntop10.push_back(pos);
            for (int i = rnk; i + 1 < top10.size(); ++i) {
               ntop10.push_back(top10[i]);
            }
            intop[pos] = true;
            intop[top10.back()] = false;
            upd(1, 1, n, pos, 0);
            upd(1, 1, n, top10.back(), a[top10.back()]);
         } else {
            ntop10.push_back(pos);
            for (int i = rnk; i < top10.size(); ++i) {
               if (top10[i] != pos) {
                  ntop10.push_back(top10[i]);
               }
            }
         }
         top10.swap(ntop10);
      } else {
         int pos;
         cin >> pos;
         if (pos == start) {
            cout << "0\n";
         } else if (pos < start) {
            int ans = start - pos;
            int val = get(1, 1, n, pos, start - 1);
            for (int v : top10) {
               if (pos <= v && v < start) val = max(val, a[v]);
            }
            int last = findR(1, 1, n, start + 1, val);
            for (int v : top10) {
               if (start < v && a[v] > val) {
                  last = min(last, v);
               }
            }
            ans += (last - 1 - start);
            cout << ans << "\n";
         } else {
            int ans = pos - start;
            int val = get(1, 1, n, start + 1, pos);
            for (int v : top10) {
               if (start < v && v <= pos) val = max(val, a[v]);
            }
            int last = findL(1, 1, n, start - 1, val);
            for (int v : top10) {
               if (v < start && a[v] > val) {
                  last = max(last, v);
               }
            }
            ans += (start - 1 - last);
            cout << ans << "\n";
         }
      }
   }
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:92:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = rnk; i + 1 < top10.size(); ++i) {
                               ~~~~~~^~~~~~~~~~~~~~
cake.cpp:101:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = rnk; i < top10.size(); ++i) {
                               ~~^~~~~~~~~~~~~~

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