oj.uz

Submission #603140

# Submission time Handle Problem Language Result Execution time Memory
603140 2022-07-23T16:01:30 Z vanic The Potion of Great Power (CEOI20_potion) C++14
56 / 100
 3000 ms 82656 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 < 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14416 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14800 KB Output is correct
2 Correct 9 ms 14800 KB Output is correct
3 Correct 9 ms 14800 KB Output is correct
4 Correct 25 ms 20020 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 82344 KB Output is correct
2 Correct 685 ms 82360 KB Output is correct
3 Correct 303 ms 59380 KB Output is correct
4 Correct 1773 ms 70292 KB Output is correct
5 Correct 864 ms 81360 KB Output is correct
6 Execution timed out 3071 ms 68608 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 82492 KB Output is correct
2 Correct 1412 ms 59028 KB Output is correct
3 Correct 1106 ms 68068 KB Output is correct
4 Correct 1715 ms 68516 KB Output is correct
5 Correct 854 ms 82656 KB Output is correct
6 Correct 1631 ms 68556 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 18244 KB Output is correct
2 Correct 101 ms 16964 KB Output is correct
3 Correct 135 ms 16740 KB Output is correct
4 Correct 830 ms 17736 KB Output is correct
5 Correct 793 ms 18136 KB Output is correct
6 Correct 119 ms 17644 KB Output is correct
7 Correct 657 ms 17136 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Correct 9 ms 14800 KB Output is correct
3 Correct 9 ms 14800 KB Output is correct
4 Correct 9 ms 14800 KB Output is correct
5 Correct 25 ms 20020 KB Output is correct
6 Correct 711 ms 82344 KB Output is correct
7 Correct 685 ms 82360 KB Output is correct
8 Correct 303 ms 59380 KB Output is correct
9 Correct 1773 ms 70292 KB Output is correct
10 Correct 864 ms 81360 KB Output is correct
11 Execution timed out 3071 ms 68608 KB Time limit exceeded
12 Halted 0 ms 0 KB -