Submission #655971

#	Time	Username	Problem	Language	Result	Execution time	Memory
655971		lunchbox1	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2134 ms	29392 KiB

potion

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100000, B = 300;
 
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() == B) {
   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() == B) {
   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