Submission #943750

#	Time	Username	Problem	Language	Result	Execution time	Memory
943750		amirhoseinfar1385	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	3038 ms	71840 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxd=100,maxq=50000+10;
int te=0,n,d,high[maxn];
struct hams{
	vector<int>timea;
	vector<vector<pair<int,int>>>allq;
	vector<set<int>>fi;
	set<int>st;
	hams(){
		timea.resize(1,0);
		allq.resize(1);
		fi.push_back(st);
	}
	void ins(int u){
		if(st.count(u)==1){
			allq.back().push_back(make_pair(te,-u));
			st.erase(u);
		}else{
			allq.back().push_back(make_pair(te,u));
			st.insert(u);
		}
		if((int)allq.back().size()==maxd){
			timea.push_back(te);
			allq.push_back({});
			fi.push_back(st);
		}
	}
	vector<int>pors(int w){
		int p=upper_bound(timea.begin(),timea.end(),w)-timea.begin();
		p--;
		set<int>fake=fi[p];
		for(auto x:allq[p]){
			if(x.first>w){
				break;
			}
			if(x.second<0){
				fake.erase(-x.second);
			}else{
				fake.insert(x.second);
			}
		}
		vector<int>ret;
		for(auto x:fake){
			ret.push_back(x);
		}
		return ret;
	}
}alle[maxn];

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

void curseChanges(int U, int A[], int B[]) {
	for(int i=1;i<=U;i++){
		te=i;
		alle[A[i-1]].ins(B[i-1]);
		alle[B[i-1]].ins(A[i-1]);
	}
}

bool cmp(int a,int b){
	return high[a]<high[b];
}

int question(int x, int y, int v) {
    vector<int>av=alle[x].pors(v);
    vector<int>dov=alle[y].pors(v);
    sort(av.begin(),av.end(),cmp);
    sort(dov.begin(),dov.end(),cmp);
    int i=0,j=0;
    if((int)av.size()==0||(int)dov.size()==0){
    	return 1000000000;
    }
    int res=1e9;
    while(i<(int)av.size()&&j<(int)dov.size()){
    	res=min(res,abs(high[av[i]]-high[dov[j]]));
    	if(high[av[i]]<high[dov[j]]){
    		i++;
    	}else{
    		j++;
    	}
    }
  	return res;
}

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