Submission #607474

#	Time	Username	Problem	Language	Result	Execution time	Memory
607474		lunchbox	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2186 ms	40512 KiB

potion

#include <bits/stdc++.h>
using namespace std;

const int N = 100000;

int n, d, u, q, h[N];
vector<vector<tuple<int, int, int>>> ev[N];
vector<int> tt[N];

void init(int n_, int d_, int h_[]) {
  n = n_, d = d_;
  for (int i = 0; i < n; i++)
    h[i] = h_[i];
}
void curseChanges(int u_, int i_[], int j_[]) {
  u = u_;
  for (int k = 1; k <= u; k++) {
    int i = i_[k - 1], j = j_[k - 1];
    if (ev[i].size() == 0 || (int) ev[i].back().size() == d) {
      if (ev[i].size() == 0)
        ev[i].push_back({});
      else  {
        sort(ev[i].back().begin(), ev[i].back().end());
        vector<pair<int, int>> v;
        for (auto [w, x, t] : ev[i].back())
          if (v.size() == 0 || v.back() != make_pair(w, x))
            v.push_back({w, x});
          else
            v.pop_back();
        ev[i].push_back({});
        for (auto [w, x] : v)
          ev[i].back().push_back(make_tuple(w, x, k - 1));
      }
      tt[i].push_back(k);
    }
    ev[i].back().push_back({h[j], j, k});
    if (ev[j].size() == 0 || (int) ev[j].back().size() == d) {
      if (ev[j].size() == 0)
        ev[j].push_back({});
      else {
        sort(ev[j].back().begin(), ev[j].back().end());
        vector<pair<int, int>> v;
        for (auto [w, x, t] : ev[j].back())
          if (v.size() == 0 || v.back() != make_pair(w, x))
            v.push_back({w, x});
          else
            v.pop_back();
        ev[j].push_back({});
        for (auto [w, x] : v)
          ev[j].back().push_back(make_tuple(w, x, k - 1));
      }
      tt[j].push_back(k);
    }
    ev[j].back().push_back({h[i], i, k});
  }
  for (int i = 0; i < n; i++)
    if (ev[i].size())
      sort(ev[i].back().begin(), ev[i].back().end());
}
int question(int i, int j, int k) {
  int p;
  if (tt[i].size() == 0 || tt[j].size() == 0 || tt[i][0] > k || tt[j][0] > k)
    return 1000000000;
  p = upper_bound(tt[i].begin(), tt[i].end(), k) - tt[i].begin() - 1;
  vector<pair<int, int>> wi;
  for (auto [w, x, t] : ev[i][p]) {
    if (t > k)
      continue;
    if (wi.size() == 0 || wi.back() != make_pair(w, x))
      wi.push_back({w, x});
    else
      wi.pop_back();
  }
  p = upper_bound(tt[j].begin(), tt[j].end(), k) - tt[j].begin() - 1;
  vector<pair<int, int>> wj;
  for (auto [w, x, t] : ev[j][p]) {
    if (t > k)
      continue;
    if (wj.size() == 0 || wj.back() != make_pair(w, x))
      wj.push_back({w, x});
    else
      wj.pop_back();
  }
  int ans = 1000000000;
  for (int l = 0, r = 0; l < (int) wi.size(); l++) {
    while (r < (int) wj.size() && wi[l].first > wj[r].first)
      ans = min(ans, wi[l].first - wj[r++].first);
    if (r < (int) wj.size())
      ans = min(ans, wj[r].first - wi[l].first);
  }
  return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30