Submission #1212004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212004		miss_robot	The Potion of Great Power (CEOI20_potion)	C++20	35 / 100	3098 ms	58104 KiB

potion

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

const int INF = 1e9, N = 2e5;
int n, u, d, s4=1;
int h[N], a[N], b[N], ans0[N], ans1[N], last0[N], last1[N];
set<int> g[N], e[N];
vector< pair<int, int> > iv0[N], iv1[N];

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

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(!s4) return;
	for(int i = 0; i < u; i++){
		if(e[a[i]].count(b[i])){
			e[a[i]].erase(b[i]), e[b[i]].erase(a[i]);
			if(h[b[i]]){
				if(!--ans1[a[i]])
					iv1[a[i]].push_back({last1[a[i]], i});
			}
			else{
				if(!--ans0[a[i]])
					iv0[a[i]].push_back({last0[a[i]], i});
			}
			if(h[a[i]]){
				if(!--ans1[b[i]])
					iv1[b[i]].push_back({last1[b[i]], i});
			}
			else{
				if(!--ans0[b[i]])
					iv0[b[i]].push_back({last0[b[i]], i});
			}
		}
		else{
			e[a[i]].insert(b[i]), e[b[i]].insert(a[i]);
			if(h[b[i]]){
				if(!ans1[a[i]]++) last1[a[i]] = i+1;
			}
			else{
				if(!ans0[a[i]]++) last0[a[i]] = i+1;
			}
			if(h[a[i]]){
				if(!ans1[b[i]]++) last1[b[i]] = i+1;
			}
			else{
				if(!ans0[b[i]]++) last0[b[i]] = i+1;
			}
		}
	}
	for(int i = 0; i < n; i++){
		if(ans0[i]) iv0[i].push_back({last0[i], u});
		if(ans1[i]) iv1[i].push_back({last1[i], u});
	}
}

int dis(int a, int b){
	return max(h[a], h[b]) - min(h[a], h[b]);
}

int st2(int X, int Y, int V){
	int sol = INF;
	vector<int> cng;
	for(int i = 0; i < V; i++){
		if(g[a[i]].count(b[i])) g[a[i]].erase(b[i]),
			g[b[i]].erase(a[i]);
		else g[a[i]].insert(b[i]), g[b[i]].insert(a[i]);
		cng.push_back(a[i]), cng.push_back(b[i]);
	}
	for(int x : g[X]) for(int y : g[Y]) sol = min(sol, dis(x, y));
	while(!cng.empty()) g[cng.back()].clear(), cng.pop_back();
	return sol;
}

int st4(int X, int Y, int V){
	int x0 = 0, x1 = 0, y0 = 0, y1 = 0;
	pair<int, int> temp = {V,INF};
	auto it0x = upper_bound(iv0[X].begin(), iv0[X].end(), temp);
	if(it0x != iv0[X].begin()){
		it0x--;
		if(it0x->second >= V) x0 = 1;
	}
	auto it1x = upper_bound(iv1[X].begin(), iv1[X].end(), temp);
	if(it1x != iv1[X].begin()){
		it1x--;
		if(it1x->second >= V) x1 = 1;
	}
	auto it0y = upper_bound(iv0[Y].begin(), iv0[Y].end(), temp);
	if(it0y != iv0[Y].begin()){
		it0y--;
		if(it0y->second >= V) y0 = 1;
	}
	auto it1y = upper_bound(iv1[Y].begin(), iv1[Y].end(), temp);
	if(it1y != iv1[Y].begin()){
		it1y--;
		if(it1y->second >= V) y1 = 1;
	}
	if((x0 && y0) || (x1 && y1)) return 0;
	if((x0 || x1) && (y0 || y1)) return 1;
	return INF;
}

int question(int X, int Y, int V){
	if(s4) return st4(X, Y, V);
	return st2(X, Y, V);
}

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