Submission #1173054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173054		Dan4Life	The Potion of Great Power (CEOI20_potion)	C++20	100 / 100	2849 ms	35908 KiB

potion

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)1e5+2;
const int mxM = (int)2e5+2;
const int C = 50;

vi v[mxN], w[mxN];
vector<vi> snap[mxN];
int n, A[mxM], B[mxM], h[mxN];

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

void upd(int ind, int x, int y){
	auto &w = snap[x][ind];
	int empty = -1, ok = 0;
	for(int i = 0; i < sz(w); i++){
		if(w[i]==-1) empty=i;
		else if(w[i]==y){
			w[i]=-1; ok = 1;
			break;
		}
	}
	if(!ok){
		if(empty==-1) w.pb(y);
		else w[empty]=y;
	}
}

void add(int i){
	int x = A[i], y = B[i];
	for(int _ : {0,1}){
		int empty = -1, ok = 0;
		for(int i = 0; i < sz(w[x]); i++){
			if(w[x][i]==-1) empty=i;
			else if(w[x][i]==y){
				w[x][i]=-1; ok = 1;
				break;
			}
		}
		if(!ok){
			if(empty==-1) w[x].pb(y);
			else w[x][empty]=y;
		}
		swap(x,y);
	}
}

void curseChanges(int m, int a[], int b[]) {
	for(int i = 0; i < n; i++) snap[i].pb(vi());
	for(int i = 1; i <= m; i++){
		A[i]=a[i-1], B[i]=b[i-1];
		if(A[i]>B[i])swap(A[i],B[i]);
		int x = A[i], y = B[i];
		v[x].pb(i); v[y].pb(i); add(i);
		if(sz(v[x])%C==0) snap[x].pb(w[x]);
		if(sz(v[y])%C==0) snap[y].pb(w[y]);
	}
}

int question(int a, int b, int r) {
	int ans = (int)1e9; if(a>b)swap(a,b);
	
	int pos = upper_bound(all(v[a]),r)-begin(v[a])-1;
	int pos2 = upper_bound(all(v[b]),r)-begin(v[b])-1;
	int ind = pos/C, ind2 = pos2/C;
	if(min(pos,pos2)==-1) return ans;
	
	for(int i = ind*C; i <= pos; i++)
		upd(ind, a, A[v[a][i]]==a?B[v[a][i]]:A[v[a][i]]);
	for(int i = ind2*C; i <= pos2; i++)
		upd(ind2, b, A[v[b][i]]==b?B[v[b][i]]:A[v[b][i]]);
	
	vi X, Y; X.clear(); Y.clear();
	for(auto x : snap[a][ind]) if(x!=-1) X.pb(h[x]);
	for(auto x : snap[b][ind2]) if(x!=-1) Y.pb(h[x]);
	sort(all(X)); sort(all(Y));
	
	for(auto x : X){
		int xd = lower_bound(all(Y), x)-begin(Y);
		if(xd<sz(Y)) ans=min(ans, Y[xd]-x);
		if(xd) ans=min(ans, x-Y[xd-1]);
	}
	
	for(int i = ind*C; i <= pos; i++)
		upd(ind, a, A[v[a][i]]==a?B[v[a][i]]:A[v[a][i]]);
	for(int i = ind2*C; i <= pos2; i++)
		upd(ind2, b, A[v[b][i]]==b?B[v[b][i]]:A[v[b][i]]);
	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