Submission #294557

#	Time	Username	Problem	Language	Result	Execution time	Memory
294557		nandonathaniel	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2551 ms	34776 KiB

potion

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005;
 
int h[MAXN],C[MAXN],n,D;
vector<pii> adj[MAXN];
vector<vector<int> > preCompute[MAXN];
 
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[]) {
	for(int i=0;i<U;i++){
		adj[A[i]].push_back({B[i],i+1});
		adj[B[i]].push_back({A[i],i+1});
	}
	for(int i=0;i<n;i++){
		C[i]=(int)sqrt((int)adj[i].size());
		if(C[i]==0)C[i]=1;
		set<int> S;
		preCompute[i].push_back(vector<int>());
		for(int j=0;j<adj[i].size();j++){
			if(S.count(adj[i][j].first)){
				S.erase(adj[i][j].first);
			}
			else S.insert(adj[i][j].first);
			if((j+1)%C[i]==0){
				preCompute[i].push_back(vector<int>());
				for(int isi : S)preCompute[i].back().push_back(isi);
			}
		}
	}
}
 
bitset<100005> stat;
 
int question(int a, int b, int d) {
	int ans=1e9;
	if(d==0){
		return ans;
	}
	int ki=0,ka=adj[a].size()-1,res=-1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		if(adj[a][mid].second<=d){
			res=mid;
			ki=mid+1;
		}
		else ka=mid-1;
	}
	stat.reset();
	vector<int> A;
	if(res!=-1){
		for(auto isi : preCompute[a][res/C[a]])stat[isi]=true;
		for(int i=(res/C[a])*C[a];i<=res;i++){
			stat[adj[a][i].first]=stat[adj[a][i].first]^1;
		}
		for(auto isi : preCompute[a][res/C[a]]){
			if(stat[isi])A.push_back(h[isi]);
		}
		for(int i=(res/C[a])*C[a];i<=res;i++){
			if(stat[adj[a][i].first])A.push_back(h[adj[a][i].first]);
		}
	}
	ki=0;ka=adj[b].size()-1;res=-1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		if(adj[b][mid].second<=d){
			res=mid;
			ki=mid+1;
		}
		else ka=mid-1;
	}
	stat.reset();
	vector<int> B;
	if(res!=-1){
		for(auto isi : preCompute[b][res/C[b]])stat[isi]=true;
		for(int i=(res/C[b])*C[b];i<=res;i++){
			stat[adj[b][i].first]=stat[adj[b][i].first]^1;
		}
		for(auto isi : preCompute[b][res/C[b]]){
			if(stat[isi])B.push_back(h[isi]);
		}
		for(int i=(res/C[b])*C[b];i<=res;i++){
			if(stat[adj[b][i].first])B.push_back(h[adj[b][i].first]);
		}
	}
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	int x=0,y=0;
	while(x<(int)A.size() && y<(int)B.size()){
		ans=min(ans,abs(A[x]-B[y]));
		if(A[x]<B[y])x++;
		else y++;
	}
	return ans;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int j=0;j<adj[i].size();j++){
      |               ~^~~~~~~~~~~~~~

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