Submission #603189

#	Time	Username	Problem	Language	Result	Execution time	Memory
603189		vanic	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2998 ms	59824 KiB

potion

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

using namespace std;

const int maxn=1e5, maxd=500;

int broj[2];
int ok[2][maxd];

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);
			}
		}
	}
	void query(int x, int koji){
		x+=n;
		while(x>0){
			for(int i=0; i<(int)t[x].size(); i++){
				ok[koji][broj[koji]++]=t[x][i];
			}
			x>>=1;
		}
	}
};

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 < 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++){
		it=poc[a[i]].lower_bound({b[i], 0});
		if(it==poc[a[i]].end() || it->first!=b[i]){
			poc[a[i]].insert({b[i], br[a[i]]});
			
			poc[b[i]].insert({a[i], br[b[i]]});
		}
		else{
			upit[a[i]].push_back({{it->second, br[a[i]]}, b[i]});
			poc[a[i]].erase(it);
			
			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);
		}
		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;
	}
	broj[0]=0;
	V[x].query(br1, 0);
	broj[1]=0;
	V[y].query(br2, 1);
	sort(ok[0], ok[0]+broj[0], cmp);
	sort(ok[1], ok[1]+broj[1], cmp);
	int pos1=0, pos2=0;
	int sol=1e9;
	while(pos1<broj[0] && pos2<broj[1]){
		sol=min(sol, abs(h[ok[0][pos1]]-h[ok[1][pos2]]));
		if(h[ok[0][pos1]]<h[ok[1][pos2]]){
			pos1++;
		}
		else{
			pos2++;
		}
	}
	return sol;
}

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