Submission #1230325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230325		ansori	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	3080 ms	38912 KiB

potion

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int BL = 50,  UU = 2e5 , NN = 1e5;
vector<int> a , b , h;
vector<pair<int , int>> f[NN];
vector<vector<int>> k[NN];
set<int> gg[NN];
int n , d;
void init(int N, int D, int H[]) {
	h = vector<int> (N , 0);
	n = N , d = D;
	for(int i = 0;i < n; ++ i) h[i] = H[i];
}

void curseChanges(int U, int A[], int B[]) {
	for(int i = 0;i < U; ++ i){
		if(A[i] > B[i]) swap(A[i] , B[i]);
		a.push_back(A[i]);
		b.push_back(B[i]);
		if(gg[a[i]].find(b[i]) == gg[a[i]].end()){
			gg[a[i]].insert(b[i]);
			gg[b[i]].insert(a[i]);
		}
		else{
			gg[a[i]].erase(b[i]);
			gg[b[i]].erase(a[i]);
		}
		f[a[i]].push_back({b[i] , i});
		if(int(f[a[i]].size()) % BL == 0){
			vector<int> pf;
			for(auto to : gg[a[i]]) pf.push_back(to);
			pf.push_back(i);
			k[a[i]].push_back(pf);
		}
		f[b[i]].push_back({a[i] , i});
		if(int(f[b[i]].size()) % BL == 0){
			vector<int> pf;
			for(auto to : gg[b[i]]) pf.push_back(to);
			pf.push_back(i);
			k[b[i]].push_back(pf);
		}
	}
}

int question(int x, int y, int v) {
	v --;
	unordered_set<int> vx , vy;
	int j = 0 , px = 0 , py = 0;
	while(j < k[x].size() and v >= k[x][j].back()) j ++;
	// cout << j << ' ';
	if(j > 0){
		for(int i = 0;i < k[x][j - 1].size() - 1; ++ i) vx.insert(k[x][j - 1][i]);
		px = j * BL;
	}
	while(px < f[x].size() and v >= f[x][px].se){
		int z = f[x][px].fi;
		if(vx.count(z)) vx.erase(z);
		else vx.insert(z);
		px ++;
	}
	j = 0;
	while(j < k[y].size() and v >= k[y][j].back()) j ++;
	//cout << j << ' ';
	if(j > 0){
		for(int i = 0;i < k[y][j - 1].size() - 1; ++ i) vy.insert(k[y][j - 1][i]);
		py = j * BL;
	}
	while(py < f[y].size() and v >= f[y][py].se){
		int z = f[y][py].fi;
		if(vy.count(z)) vy.erase(z);
		else vy.insert(z);
		py ++;
	}
	vector<int> hx , hy;
	//cout << x << ' ' << y << ' ';
	for(auto to : vx){
		//cout << to << ' ';
		hx.push_back(h[to]);
	}
	for(auto to : vy){
		//cout << to << ' ';
		hy.push_back(h[to]);
	}
	if(hx.size() == 0 or hy.size() == 0) return 1000000000;
	sort(hx.begin() , hx.end());
	sort(hy.begin() , hy.end());
	int answ = 1e9 , s = hy.size();
	j = 0;
	for(auto to : hx){
		while(j < s and hy[j] <= to) j ++;
		answ = min({answ , abs(to - hy[max(0 , j - 1)]) , abs(to - hy[min(s - 1 , j)])});
	}
    return answ;
}

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