oj.uz

답안 #603184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603184 2022-07-23T16:39:34 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);
			}
		}
	}
	void query(int x, vector < int > &sol){
		x+=n;
		while(x>0){
			for(int i=0; i<(int)t[x].size(); i++){
				sol.push_back(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;
	}
	vector < int > v1, v2;
	V[x].query(br1, v1);
	V[y].query(br2, v2);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9936 KB Output is correct
2 Correct 10 ms 9936 KB Output is correct
3 Correct 9 ms 9956 KB Output is correct
4 Correct 25 ms 15192 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 58248 KB Output is correct
2 Correct 540 ms 58356 KB Output is correct
3 Correct 299 ms 54600 KB Output is correct
4 Correct 1708 ms 56172 KB Output is correct
5 Correct 789 ms 54376 KB Output is correct
6 Execution timed out 3058 ms 58624 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 58200 KB Output is correct
2 Correct 1279 ms 54320 KB Output is correct
3 Correct 978 ms 58028 KB Output is correct
4 Correct 1497 ms 58404 KB Output is correct
5 Correct 774 ms 58756 KB Output is correct
6 Correct 1787 ms 58552 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 12588 KB Output is correct
2 Correct 101 ms 12136 KB Output is correct
3 Correct 175 ms 11996 KB Output is correct
4 Correct 952 ms 12560 KB Output is correct
5 Correct 936 ms 12600 KB Output is correct
6 Correct 122 ms 11984 KB Output is correct
7 Correct 702 ms 12372 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 7 ms 9936 KB Output is correct
3 Correct 10 ms 9936 KB Output is correct
4 Correct 9 ms 9956 KB Output is correct
5 Correct 25 ms 15192 KB Output is correct
6 Correct 538 ms 58248 KB Output is correct
7 Correct 540 ms 58356 KB Output is correct
8 Correct 299 ms 54600 KB Output is correct
9 Correct 1708 ms 56172 KB Output is correct
10 Correct 789 ms 54376 KB Output is correct
11 Execution timed out 3058 ms 58624 KB Time limit exceeded
12 Halted 0 ms 0 KB -