Submission #603140

#	Time	Username	Problem	Language	Result	Execution time	Memory
603140		vanic	The Potion of Great Power (CEOI20_potion)	C++14	56 / 100	3071 ms	82656 KiB

potion

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int maxn=1e5+5;

struct tournament{
	vector < vector < int > > t;
	int n;
	tournament(int sz){
		n=sz;
		for(int i=0; i<n*2; i++){
			t.push_back({});
		}
	}
	
	void update(int l, int r, int val){
		for(l+=n, r+=n; l<r; l>>=1, r>>=1){
			if(l&1){
				t[l++].push_back(val);
			}
			if(r&1){
				t[--r].push_back(val);
			}
		}
	}
	vector < int > query(int x){
		x+=n;
		vector < int > sol;
		while(x>0){
			for(int i=0; i<(int)t[x].size(); i++){
				sol.push_back(t[x][i]);
			}
			x>>=1;
		}
		return sol;
	}
};

int n, d;
int h[maxn];

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

int br[maxn];
vector < int > kad[maxn];
set < int > provj[maxn];
set < pair < int, int > > poc[maxn];
vector < pair < pair < int, int >, int > > upit[maxn];

vector < tournament > V;

void curseChanges(int u, int a[], int b[]){
	set < pair < int, int > >::iterator it;
	for(int i=0; i<u; i++){
		if(provj[a[i]].find(b[i])==provj[a[i]].end()){
			poc[a[i]].insert({b[i], br[a[i]]});
			provj[a[i]].insert(b[i]);
			
			poc[b[i]].insert({a[i], br[b[i]]});
			provj[b[i]].insert(a[i]);
		}
		else{
			it=poc[a[i]].lower_bound({b[i], 0});
			upit[a[i]].push_back({{it->second, br[a[i]]}, b[i]});
			poc[a[i]].erase(it);
			provj[a[i]].erase(b[i]);
			
			it=poc[b[i]].lower_bound({a[i], 0});
			upit[b[i]].push_back({{it->second, br[b[i]]}, a[i]});
			poc[b[i]].erase(it);
			provj[b[i]].erase(a[i]);
		}
		br[a[i]]++;
		br[b[i]]++;
		kad[a[i]].push_back(i+1);
		kad[b[i]].push_back(i+1);
	}
	for(int i=0; i<n; i++){
		tournament T(br[i]);
		while(!upit[i].empty()){
			T.update(upit[i].back().first.first, upit[i].back().first.second, upit[i].back().second);
			upit[i].pop_back();
		}
		while(!poc[i].empty()){
			T.update(poc[i].begin()->second, br[i], poc[i].begin()->first);
			poc[i].erase(poc[i].begin());
		}
		V.push_back(T);
	}
}


int binary(int x, int val){
	int lo=-1, hi=kad[x].size()-1, mid;
	while(lo<hi){
		mid=(lo+hi+1)/2;
		if(kad[x][mid]>val){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
	}
	return lo;
}

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

int question(int x, int y, int v){
	int br1=binary(x, v);
	int br2=binary(y, v);
	if(br1==-1 || br2==-1){
		return 1e9;
	}
	vector < int > v1=V[x].query(br1);
	vector < int > v2=V[y].query(br2);
	sort(v1.begin(), v1.end(), cmp);
	sort(v2.begin(), v2.end(), cmp);
	int pos1=0, pos2=0;
	int sol=1e9;
	while(pos1<(int)v1.size() && pos2<(int)v2.size()){
		sol=min(sol, abs(h[v1[pos1]]-h[v2[pos2]]));
		if(h[v1[pos1]]<h[v2[pos2]]){
			pos1++;
		}
		else{
			pos2++;
		}
	}
	return sol;
}

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