oj.uz

Submission #603156

# Submission time Handle Problem Language Result Execution time Memory
603156 2022-07-23T16:09:09 Z vanic The Potion of Great Power (CEOI20_potion) C++14
56 / 100
 3000 ms 58756 KB 
#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 < 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;
	}
	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 / 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 8 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 24 ms 15240 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 58248 KB Output is correct
2 Correct 550 ms 58200 KB Output is correct
3 Correct 253 ms 54704 KB Output is correct
4 Correct 1621 ms 56176 KB Output is correct
5 Correct 751 ms 54184 KB Output is correct
6 Execution timed out 3029 ms 58588 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 58248 KB Output is correct
2 Correct 1256 ms 54280 KB Output is correct
3 Correct 987 ms 58208 KB Output is correct
4 Correct 1433 ms 58420 KB Output is correct
5 Correct 699 ms 58756 KB Output is correct
6 Correct 1530 ms 58624 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 82 ms 12232 KB Output is correct
3 Correct 134 ms 12044 KB Output is correct
4 Correct 846 ms 12488 KB Output is correct
5 Correct 857 ms 12556 KB Output is correct
6 Correct 107 ms 11944 KB Output is correct
7 Correct 655 ms 12316 KB Output is correct

Subtask #6
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 8 ms 9936 KB Output is correct
4 Correct 7 ms 9936 KB Output is correct
5 Correct 24 ms 15240 KB Output is correct
6 Correct 563 ms 58248 KB Output is correct
7 Correct 550 ms 58200 KB Output is correct
8 Correct 253 ms 54704 KB Output is correct
9 Correct 1621 ms 56176 KB Output is correct
10 Correct 751 ms 54184 KB Output is correct
11 Execution timed out 3029 ms 58588 KB Time limit exceeded
12 Halted 0 ms 0 KB -