Submission #1289357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289357		loom	The Potion of Great Power (CEOI20_potion)	C++20	0 / 100	158 ms	58992 KiB

potion

#include<bits/stdc++.h>
using namespace std;
#define inf (int)1e9
#define nl '\n'

const int N = 1e5+1, c = 20;
vector<pair<int, vector<int>>> g[N]; 
int h[N], cnt[N];
int n;

void init(int N, int D, int H[]){
   n = N;
   for(int i = 0; i < n; i++) h[i] = H[i];
}

void curseChanges(int u, int a[], int b[]){
   set<int> cg[n];

   for(int i = 1; i <= u; i++){
      auto add = [&](int x, int y){
         auto &cgx = cg[x];

         if(cgx.count(y)) cgx.erase(y);
         else cgx.insert(y);

         if(g[x].size() % c != 0) g[x].push_back({i, {y}});
         else g[x].push_back({i, vector<int>(cgx.begin(), cgx.end())});
      };

      add(a[i-1], b[i-1]);
      add(b[i-1], a[i-1]);
   } 
}

vector<int> get(int x, int d){
   auto &gx = g[x];
   int n = gx.size();

   vector<int> v = {inf};
   int r = upper_bound(gx.begin(), gx.end(), pair(d, v)) - gx.begin() - 1;

   if(r < 0) return {};
   int l = r - (r % c);

   auto cmp = [&](int x, int y){
      return h[x] < h[y];
   };

   for(int y : gx[l].second) cnt[y]++;

   for(int i = l+1; i <= r; i++){
      int y = gx[i].second[0];
      cnt[y]++;
   }

   v.clear();

   for(int y : gx[l].second){
      if(cnt[y] % 2) v.push_back(h[y]);
   }

   for(int i = l+1; i <= r; i++){
      int y = gx[i].second[0];
      if(cnt[y] % 2) v.push_back(h[y]);
   }

   sort(v.begin(), v.end());
   return v;
}

int question(int p, int q, int v){
   auto v1 = get(p, v);
   auto v2 = get(q, v);

   int s1 = v1.size(), s2 = v2.size();
   int ans = inf;

   for(int i = 0, j = -1; i < s1; i++){
      while(j+1 < s2 and v2[j+1] <= v1[i]) j++;
      ans = min(ans, min(j >= 0 ? v1[i] - v2[j] : inf, j+1 < s2 ? v2[j+1] - v1[i] : inf));
   }

   return ans;
}

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