Submission #1159255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159255		shn	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	619 ms	327680 KiB

potion

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
using namespace std;
#define pb push_back
#define len(s) (int)(s.size())
#define F first
#define S second
#define pll pair < int , int >

const int N = 2e5;

int n , d , h[N];
int u , a[N], b[N];

pll last[N];

vector < int > g[N][2];

vector < int > f[N];

map < pll , int > mp;

mt19937 rng(time(0));

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 A[], int B[]) {
	u = U;
	for(int i = 0; i < u; i++){
		a[i] = A[i];
		b[i] = B[i];
		if(!last[a[i]].F) g[i][0].pb(b[i]);
		else{
			for(int it : g[last[a[i]].F - 1][last[a[i]].S]) g[i][0].pb(it);
			if(!mp[{a[i] , b[i]}]) g[i][0].pb(b[i]);
			else{
				vector < int > zam;
				for(int it : g[i][0]){
					if(it != b[i]) zam.pb(it);
				}
				g[i][0].clear();
				for(int it : zam) g[i][0].pb(it);
			}
		}
		if(!last[b[i]].F) g[i][1].pb(a[i]);
		else{
			for(int it : g[last[b[i]].F - 1][last[b[i]].S]) g[i][1].pb(it);
			if(!mp[{a[i] , b[i]}]) g[i][1].pb(a[i]);
			else{
				vector < int > zam;
				for(int it : g[i][1]){
					if(it != a[i]) zam.pb(it);
				}
				g[i][1].clear();
				for(int it : zam) g[i][1].pb(it);
			}
		}
		last[a[i]] = {i + 1 , 0};
		last[b[i]] = {i + 1 , 1};
		mp[{a[i] , b[i]}] ^= 1;
		mp[{b[i] , a[i]}] ^= 1;
		f[a[i]].pb(i);
		f[b[i]].pb(i);
	}
}

int find(int x , int w){
	int l = 0 , r = len(f[x]) - 1 , res = u;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(f[x][mid] < w){
			l = mid + 1;
			res = mid;
		}
		else{
			r = mid - 1;
		}
	}
	return res;
}

int question(int x, int y, int v) {
	int lstx = find(x , v) , lsty = find(y , v);
	if(lstx == u || lsty == u) return 1000000000;
	int mn = 1000000000;
	int c = 0 , d = 0;
	if(a[f[x][lstx]] != x) c++;
	if(a[f[y][lsty]] != y) d++;
	// for(int it : f[x]){
		// cout << it << ' ';
	// }
	// cout << '\n';
	// cout << lstx << ' ' << lsty << '\n' << '\n';
	// for(int it : g[f[x][lstx]][c]){
		// cout << it << ' ';
	// }
	// cout << '\n';
	// for(int it2 : g[f[y][lsty]][d]){
		// cout << it2 << ' ';
	// }
	// cout << '\n';
	for(int it : g[f[x][lstx]][c]){
		for(int it2 : g[f[y][lsty]][d]){
			mn = min(mn , abs(h[it] - h[it2]));
		}
	}
	return mn;
}

// int slow(int x , int y , int v){
	// set < int > st , t;
	// map < int , int > e , j;
	// for(int i = 0; i < v; i++){
		// if(a[i] == x){
			// if(e[b[i]]) st.erase(b[i]);
			// else st.insert(b[i]);
			// e[b[i]] ^= 1;
		// }
		// else if(b[i] == x){
			// if(e[a[i]]) st.erase(a[i]);
			// else st.insert(a[i]);
			// e[a[i]] ^= 1;
		// }
		// if(b[i] == y){
			// if(j[a[i]]) t.erase(a[i]);
			// else t.insert(a[i]);
			// j[a[i]] ^= 1;
		// }
		// else if(a[i] == y){
			// if(j[b[i]]) t.erase(b[i]);
			// else t.insert(b[i]);
			// j[b[i]] ^= 1;
		// }
	// }
	// // for(int it : st){
		// // cout << it << ' ';
	// // }
	// // cout << '\n';
	// // for(int it : t){
		// // cout << it << ' ';
	// // }
	// // cout << '\n';
	// int mn = 1000000000;
	// for(int it : st){
		// for(int it2 : t){
			// mn = min(mn , abs(h[it] - h[it2]));
		// }
	// }
	// return mn;
// }

// int main(){
	// int N , D;
	// cin >> N >> D;
	// int H[N];
	// for(int i = 0; i < N; i++) cin >> H[i];
	// init(N, D, H);
	// int U;
	// cin >> U;
	// int A[U], B[U];
	// for(int i = 0; i < U; i++) cin >> A[i];
	// for(int i = 0; i < U; i++) cin >> B[i];
	// curseChanges(U , A , B);
	// while(1){
		// int x = rng() % N , y = rng() % N , v = rng() % U;
		// if(x == y) continue;
		// if(question(x , y , v) != slow(x , y , v)){
			// cout << x << ' ' << y << ' ' << v << '\n';
			// return 0;
		// }
	// }
	// // cout << question(5 , 4 , 10) << '\n';
	// // cout << slow(5 , 4 , 10) << '\n';
// }

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