Submission #1134158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134158		stefanneagu	Cake (CEOI14_cake)	C++20	0 / 100	1809 ms	24472 KiB

cake

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 5e5 + 1, inf = 1e18;

int v[nmax], f[10];
int ms[nmax], md[nmax];
int n, p;
set<pair<int, int>> lant, val;
set<int> st, dr;

void build() {
  stack<int> s;
  for(int i = 1; i <= n; i++) {
    if(s.empty()) {
      s.push(i);
    } else {
      while(s.size() && v[s.top()] < v[i]) {
        md[s.top()] = i;
        s.pop();
      }
      s.push(i);
    }
  }
  while(s.size()) {
    md[s.top()] = n + 1;
    s.pop();
  }
  for(int i = n; i >= 1; i--) {
    if(s.empty()) {
      s.push(i);
    } else {
      while(s.size() && v[s.top()] < v[i]) {
        ms[s.top()] = i;
        s.pop();
      }
      s.push(i);
    }
  }
  while(s.size()) {
    ms[s.top()] = 0;
    s.pop();
  }
  int sp;
  if(p == n || v[p - 1] < v[p + 1]) {
    sp = p - 1;
  } else {
    sp = p + 1;
  }
  lant.insert({v[sp], sp});
  while(0 < sp && sp < n + 1) {
    if(sp < p) {
      sp = md[sp];
    } else {
      sp = ms[sp];
    }
    lant.insert({v[sp], sp});
  }
  val.insert({inf, sp});
  if(sp == 0) {
    sp = n + 1;
  } else {
    sp = 0;
  }
  v[sp] = inf + 1;
  lant.insert({inf + 1, sp});
  val.insert({inf + 1, sp});
  for(auto it : lant) {
    if(it.second < p) {
      st.insert(it.second);
    } else {
      dr.insert(-it.second);
    }
  }
  lant.insert({-inf, p});
}

int32_t main() {
  cin >> n >> p;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    if(v[i] >= n - 9) {
      v[i] = n - 9 + nmax * (v[i] - n + 9);
    }
    val.insert({v[i], i});
  }
  v[p] = -inf;
  v[n + 1] = v[0] = inf;
  build();
  int q;
  cin >> q;
  while(q--) {
    char ch;
    cin >> ch;
    if(ch == 'F') {
      int a;
      cin >> a;
      if(a == p) {
        cout << "0\n";
        continue;
      }
      int ult = 0;
      if(a < p) {
        ult = *st.lower_bound(a);
      } else {
        ult = -*dr.lower_bound(-a);
      }
      auto it = lant.find({v[ult], ult});
      // assert(it != lant.begin());
      // cout << (*it).second << '\n';
      it++;
      cout << abs(a - (int) (*it).second) - 1 << '\n';
    } else {
      int ii, ai;
      cin >> ii >> ai;
      if(ii == p) {
        continue;
      }
      ai--;
      val.erase({v[ii], ii});
      f[ai]++;
      v[ii] = n - 9 + nmax * (9 - ai) + f[ai];
      val.insert({v[ii], ii});
      // deci vedem daca
      // val pe care ar inlocui o
      // e mai mica
      vector<pair<int, int>> t10;
      for(int j = 1; j <= 12 && val.size(); j++) {
        auto it = val.rbegin();
        t10.push_back(*it);
        val.erase(*val.rbegin());
      }
      for(auto it : t10) {
        val.insert(it);
      }
      sort(t10.begin(), t10.end());
      while(true) {
        if(lant.empty()) {
          assert(0);
          break;
        }
        if((*lant.rbegin()).second != ii && (*lant.rbegin()).first < t10[0].first) {
          break;
        }
        if((*lant.rbegin()).second < p) {
          st.erase((*lant.rbegin()).second);
        } else {
          dr.erase(-(*lant.rbegin()).second);
        }
        lant.erase(*lant.rbegin());
      }
      // reconstruim
      int sp;
      if(lant.size() == 1) {
        if(p == n || v[p - 1] < v[p + 1]) {
          sp = p - 1;
        } else {
          sp = p + 1;
        }
      } else {
        sp = (*lant.begin()).second;
      }
      val.erase({v[0], 0});
      val.erase({v[n + 1], n + 1});
      v[0] = v[n + 1] = inf;
      lant.insert({v[sp], sp});
      if(sp < p) {
        st.insert(sp);
      } else {
        dr.insert(-sp);
      }
      while(sp != 0 && sp != inf) {
        int nou;
        if(sp < p) {
          nou = n + 1;
          for(auto it : t10) {
            if(it.first > v[sp] && it.second > p) {
              nou = min(nou, it.second);
            }
          }
          st.insert(nou);
        } else {
          nou = 0;
          for(auto it : t10) {
            if(it.first > v[sp] && it.second < p) {
              nou = max(nou, it.second);
            }
          }
          dr.insert(-nou);
        }
        sp = nou;
        lant.insert({v[sp], sp});
      }
      val.insert({v[sp], sp});
      if(sp == n + 1) {
        sp = 0;
      } else {
        sp = n + 1;
      }
      v[sp]++;
      val.insert({v[sp], sp});
      if(sp < p) {
        st.insert(sp);
      } else {
        dr.insert(-sp);
      }
    }
  }
  return 0;
}

/*
5 3
5 1 2 4 3
5
F 1
F 2
F 3
F 4
F 5
*/

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