제출 #943757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943757		amirhoseinfar1385	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2791 ms	126020 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxd=42,maxq=50000+10;
int te=0,n,d,high[maxn];
struct cmp {
    bool operator() (int a, int b) const {
        if(high[a]!=high[b]){
        	return high[a]<high[b];
        }
        return a<b;
    }
};
struct hams{
	vector<int>timea;
	vector<vector<pair<int,int>>>allq;
	vector<set<int,cmp>>fi;
	set<int,cmp>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,cmp>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);
    int i=0,j=0;
    int res=1000000000;
    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]]){
    		if(i+1==(int)av.size()){
    			j++;
    		}else if(j+1==(int)dov.size()){
    			i++;
    		}else if(high[av[i+1]]<high[dov[j+1]]){
    			i++;
    		}else{
    			j++;
    		}
    		continue;
    	}
    	if(high[av[i]]<high[dov[j]]){
    		i++;
    	}else{
    		j++;
    	}
    }
  	return res;
}

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