Submission #578089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
578089	2022-06-16T04:01:08 Z	amunduzbaev	The Potion of Great Power (CEOI20_potion)	C++17	14 / 100	2453 ms	37924 KB

potion

#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
const int N = 1e5 + 5;
vector<ar<int, 2>> edges[N];
multiset<int> S[N];
int h[N];

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

void curseChanges(int U, int A[], int B[]) {
	set<ar<int, 2>> ss;
	for(int i=0;i<U;i++){
		if(A[i] > B[i]) swap(A[i], B[i]);
		int t = 1;
		if(ss.count({A[i], B[i]})) t = -1;
		if(t == 1){
			S[A[i]].insert(h[B[i]]);
			S[B[i]].insert(h[A[i]]);
		} else {
			S[A[i]].erase(S[A[i]].find(h[B[i]]));
			S[B[i]].erase(S[B[i]].find(h[A[i]]));
		}
		//~ edges[A[i]].push_back({i + 1, (B[i] + 1) * t});
		//~ edges[B[i]].push_back({i + 1, (A[i] + 1) * t});
		if(t == 1) ss.insert({A[i], B[i]});
		else ss.erase({A[i], B[i]});
	}
	
	
}

int question(int x, int y, int v) {
	//~ multiset<int> a, b;
	//~ for(auto u : S[x]) a.insert(h[u]);
	//~ for(auto u : S[y]) b.insert(h[u]);
	//~ cout<<"here"<<endl;
	//~ for(auto u : edges[x]){
		//~ if(u[0] > v) break;
		//~ if(u[1] < 0){
			//~ a.erase(a.find(h[-u[1] - 1]));
		//~ } else {
			//~ a.insert(h[u[1] - 1]);
		//~ }
	//~ }
	
	//~ for(auto u : edges[y]){
		//~ if(u[0] > v) break;
		//~ if(u[1] < 0){
			//~ b.erase(b.find(h[-u[1] - 1]));
		//~ } else {
			//~ b.insert(h[u[1] - 1]);
		//~ }
	//~ }
	
	int res = 1e9;
	for(auto x : S[x]){
		auto it = S[y].lower_bound(x);
		if(it != S[y].end()){
			res = min(res, *it - x);
		} if(it != S[y].begin()){
			it--;
			res = min(res, x - *it);
		}
	}
	
	return res;
}

/*

6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26 
3 0 8 0
0 5 5 1000000000
3 0 11 14

*/

Subtask #1
0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	7248 KB	Incorrect
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	7504 KB	Incorrect
2	Halted	0 ms	0 KB	-

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	428 ms	37892 KB	Output is correct
2	Correct	432 ms	37780 KB	Output is correct
3	Correct	157 ms	9744 KB	Output is correct
4	Correct	1888 ms	22864 KB	Output is correct
5	Correct	802 ms	36904 KB	Output is correct
6	Correct	2453 ms	17640 KB	Output is correct
7	Correct	533 ms	17776 KB	Output is correct