Submission #1289379

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

potion

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

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

bool cmp(int x, int y){
   return h[x] < h[y];
}

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}});
            return;
         }

         vector<int> v(cgx.begin(), cgx.end());
         sort(v.begin(), v.end(), cmp);
         g[x].push_back({i, v});
      };

      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];
   };

   auto &cg = gx[l].second;
   set<int> st;

   for(int i = l+1; i <= r; i++){
      int y = gx[i].second[0];
      
      if(st.count(y)) st.erase(y);
      else st.insert(y);
   }

   vector<int> ng(st.begin(), st.end());
   sort(ng.begin(), ng.end(), cmp);

   v.resize(cg.size() + ng.size());
   merge(cg.begin(), cg.end(), ng.begin(), ng.end(), v.begin());

   vector<int> res;
   for(int i = 0; i+1 < (int)v.size(); i++){
      if(v[i] == v[i+1]) i++;
      else res.push_back(h[v[i]]); 
   }

   return res;
}

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