Submission #1289045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289045		loom	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	3094 ms	257712 KiB

potion

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

const int N = 1e5+1, l = 4255, k = 48;
int h[N], a[2*N], b[2*N];
vector<int> sg[k][N];

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

void curseChanges(int u, int A[], int B[]){
   unordered_map<int,int> g[N];

   for(int i = 1; i <= u; i++){
      a[i] = A[i-1];
      b[i] = B[i-1];
      int x = a[i], y = b[i];

      g[x][y]++;
      g[y][x]++;

      if(i % l == 0){
         int div = i/l;

         for(int j = 0; j < N; j++){
            sg[div][j].reserve(g[j].size());

            for(auto &[z, c] : g[j]){
               if(c % 2) sg[div][j].push_back(z);
            }
         }
      }
   } 
}

int question(int p, int q, int v){
   int div = v/l;
   auto &cg = sg[div];

   unordered_map<int,int> gp, gq;

   for(int &x : cg[p]) gp[x]++;
   for(int &x : cg[q]) gq[x]++;

   for(int i = div * l + 1; i <= v; i++){
      int x = a[i], y = b[i];

      if(x == p) gp[y]++;
      if(x == q) gq[y]++;
      if(y == p) gp[x]++;
      if(y == q) gq[x]++;
   }

   vector<int> v1, v2;

   for(auto &[x, c] : gp){
      if(c % 2) v1.push_back(h[x]);
   }
   for(auto &[x, c] : gq){
      if(c % 2) v2.push_back(h[x]);
   }

   sort(v1.begin(), v1.end());
   sort(v2.begin(), v2.end());

   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: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30