oj.uz

Submission #912249

# Submission time Handle Problem Language Result Execution time Memory
912249 2024-01-19T08:57:43 Z pcc The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 45640 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

using namespace std;
const int inf = 1e9;
const int mxn = 2e5+10;
int arr[mxn];
int N,D,U;
pii ev[mxn];
vector<ll> bit[mxn];

void init(int NN, int DD, int H[]) {
	N = NN,D = D;
	for(int i = 0;i<N;i++)arr[i] = H[i];
	return;
}

void modify(int p,ll v){
	for(;p<mxn;p+=p&-p){
		bit[p].push_back(v);
	}
	return;
}

void curseChanges(int UU, int A[], int B[]) {
	U = UU;
	for(int i = 1;i<=U;i++){
		ev[i] = make_pair(A[i-1],B[i-1]);
		modify(i,1ll*ev[i].fs*mxn+ev[i].sc);
		modify(i,1ll*ev[i].sc*mxn+ev[i].fs);
	}
	for(int i = 1;i<=U;i++){
		vector<ll> tmp;
		swap(tmp,bit[i]);
		sort(tmp.begin(),tmp.end());
		for(auto &j:tmp){
			if(!bit[i].empty()&&bit[i].back() == j)bit[i].pop_back();
			else bit[i].push_back(j);
		}
		//cout<<i<<":";for(auto &j:bit[i])cout<<j<<',';cout<<endl;
	}
	return;
}

vector<int> getval(int p,int tar){
	ll s = 1ll*tar*mxn,e = 1ll*tar*mxn+mxn-1;
	vector<int> re;
	for(;p>0;p-= p&-p){
		auto lit = lower_bound(bit[p].begin(),bit[p].end(),s);
		auto rit = upper_bound(bit[p].begin(),bit[p].end(),e);
		for(auto it = lit;it != rit;it++){
			re.push_back(*it-1ll*tar*mxn);
		}
	}
	vector<int> tmp;
	swap(tmp,re);
	sort(tmp.begin(),tmp.end());
	for(auto &i:tmp){
		if(!re.empty()&&re.back() == i)re.pop_back();
		else re.push_back(i);
	}
	return re;
}

int question(int x, int y, int t) {
	auto v1 = getval(t,x);
	auto v2 = getval(t,y);
	/*
	for(auto &i:v1)cout<<i<<',';cout<<endl;
	for(auto &i:v2)cout<<i<<',';cout<<endl;

   */
	for(auto &i:v1)i = arr[i];
	for(auto &i:v2)i = arr[i];
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	int ans = 1e9;
	for(auto &i:v1){
		auto it = lower_bound(v2.begin(),v2.end(),i);
		if(it != v2.end())ans = min(ans,abs(*it-i));
		if(it != v2.begin()){
			it--;
			ans = min(ans,abs(*it-i));
		}
	}
	return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7000 KB Output is correct
2 Correct 4 ms 7000 KB Output is correct
3 Correct 4 ms 7000 KB Output is correct
4 Correct 12 ms 8132 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 45636 KB Output is correct
2 Correct 387 ms 45640 KB Output is correct
3 Correct 412 ms 41188 KB Output is correct
4 Correct 1856 ms 44056 KB Output is correct
5 Correct 576 ms 44644 KB Output is correct
6 Execution timed out 3016 ms 42836 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 45600 KB Output is correct
2 Execution timed out 3042 ms 41704 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 9364 KB Output is correct
2 Correct 143 ms 9416 KB Output is correct
3 Correct 250 ms 9164 KB Output is correct
4 Correct 1006 ms 8980 KB Output is correct
5 Correct 998 ms 9500 KB Output is correct
6 Correct 162 ms 9036 KB Output is correct
7 Correct 1115 ms 8908 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 4 ms 7000 KB Output is correct
3 Correct 4 ms 7000 KB Output is correct
4 Correct 4 ms 7000 KB Output is correct
5 Correct 12 ms 8132 KB Output is correct
6 Correct 396 ms 45636 KB Output is correct
7 Correct 387 ms 45640 KB Output is correct
8 Correct 412 ms 41188 KB Output is correct
9 Correct 1856 ms 44056 KB Output is correct
10 Correct 576 ms 44644 KB Output is correct
11 Execution timed out 3016 ms 42836 KB Time limit exceeded
12 Halted 0 ms 0 KB -