oj.uz

Submission #603189

# Submission time Handle Problem Language Result Execution time Memory
603189 2022-07-23T16:43:51 Z vanic The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2998 ms 59824 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9936 KB Output is correct
2 Correct 6 ms 9936 KB Output is correct
3 Correct 6 ms 9936 KB Output is correct
4 Correct 27 ms 15224 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 58344 KB Output is correct
2 Correct 520 ms 58256 KB Output is correct
3 Correct 243 ms 54676 KB Output is correct
4 Correct 1529 ms 56244 KB Output is correct
5 Correct 698 ms 54232 KB Output is correct
6 Correct 2913 ms 58736 KB Output is correct
7 Correct 605 ms 57432 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 58336 KB Output is correct
2 Correct 1090 ms 54264 KB Output is correct
3 Correct 929 ms 58072 KB Output is correct
4 Correct 1238 ms 58408 KB Output is correct
5 Correct 623 ms 58864 KB Output is correct
6 Correct 1405 ms 58652 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 12492 KB Output is correct
2 Correct 70 ms 12224 KB Output is correct
3 Correct 122 ms 12040 KB Output is correct
4 Correct 757 ms 12560 KB Output is correct
5 Correct 728 ms 12604 KB Output is correct
6 Correct 87 ms 11932 KB Output is correct
7 Correct 595 ms 12372 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 6 ms 9936 KB Output is correct
4 Correct 6 ms 9936 KB Output is correct
5 Correct 27 ms 15224 KB Output is correct
6 Correct 561 ms 58344 KB Output is correct
7 Correct 520 ms 58256 KB Output is correct
8 Correct 243 ms 54676 KB Output is correct
9 Correct 1529 ms 56244 KB Output is correct
10 Correct 698 ms 54232 KB Output is correct
11 Correct 2913 ms 58736 KB Output is correct
12 Correct 605 ms 57432 KB Output is correct
13 Correct 526 ms 58336 KB Output is correct
14 Correct 1090 ms 54264 KB Output is correct
15 Correct 929 ms 58072 KB Output is correct
16 Correct 1238 ms 58408 KB Output is correct
17 Correct 623 ms 58864 KB Output is correct
18 Correct 1405 ms 58652 KB Output is correct
19 Correct 49 ms 12492 KB Output is correct
20 Correct 70 ms 12224 KB Output is correct
21 Correct 122 ms 12040 KB Output is correct
22 Correct 757 ms 12560 KB Output is correct
23 Correct 728 ms 12604 KB Output is correct
24 Correct 87 ms 11932 KB Output is correct
25 Correct 595 ms 12372 KB Output is correct
26 Correct 777 ms 53928 KB Output is correct
27 Correct 1369 ms 58104 KB Output is correct
28 Correct 1561 ms 59824 KB Output is correct
29 Correct 1469 ms 56120 KB Output is correct
30 Correct 2998 ms 58632 KB Output is correct
31 Correct 2432 ms 54908 KB Output is correct
32 Correct 2507 ms 58724 KB Output is correct