oj.uz

Submission #912246

# Submission time Handle Problem Language Result Execution time Memory
912246 2024-01-19T08:56:12 Z pcc The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 1118 ms 44692 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 = 1e5+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 1 ms 2648 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3072 KB Output is correct
2 Correct 3 ms 3072 KB Output is correct
3 Correct 3 ms 3068 KB Output is correct
4 Correct 11 ms 4084 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 44692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 44092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 5200 KB Output is correct
2 Correct 144 ms 4688 KB Output is correct
3 Correct 266 ms 4944 KB Output is correct
4 Correct 1002 ms 5196 KB Output is correct
5 Correct 986 ms 5200 KB Output is correct
6 Correct 169 ms 4932 KB Output is correct
7 Correct 1118 ms 4688 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 3 ms 3072 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 11 ms 4084 KB Output is correct
6 Runtime error 122 ms 44692 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -