oj.uz

Submission #578477

# Submission time Handle Problem Language Result Execution time Memory
578477 2022-06-17T04:04:35 Z amunduzbaev The Potion of Great Power (CEOI20_potion) C++17
56 / 100
 3000 ms 112080 KB 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ar array
const int N = 1e5 + 5;
const int C = 40;
vector<ar<int, 2>> edges[N];
vector<multiset<int>> vals[N];
vector<int> tim[N];
int h[N], n;
 
void init(int N, int D, int H[]) {
	n = N;
	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;
		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]});
	}
	
	for(int i=0;i<n;i++){
		multiset<int> ss;
		for(int j=0;j<(int)edges[i].size();j++){
			if(j % C == 0){
				vals[i].push_back(ss);
				tim[i].push_back(edges[i][j][0]);
			}
			
			if(edges[i][j][1] < 0){
				ss.erase(ss.find(h[-edges[i][j][1] - 1]));
			} else {
				ss.insert(h[edges[i][j][1] - 1]);
			}
		}
	}
	
	//~ for(int i=0;i<n;i++){
		//~ cout<<i<<"\n";
		//~ for(auto x : edges[i]) cout<<x[0]<<" "<<x[1]<<"\n";
		//~ cout<<"\n";
	//~ } 
}
 
multiset<int> get(int a, int t){
	int j = upper_bound(tim[a].begin(), tim[a].end(), t) - tim[a].begin();
	if(!j){
		return {};
	} j--;
	
	multiset<int> res = vals[a][j];
	for(int k=j*C;k<(int)edges[a].size() && edges[a][k][0]<=t;k++){
		if(edges[a][k][1] > 0){
			res.insert(h[edges[a][k][1] - 1]);
		} else {
			res.erase(res.find(h[-edges[a][k][1] - 1]));
		}
	}
	
	return res;
}
 
int question(int x, int y, int v) {
	multiset<int> a = get(x, v);
	multiset<int> b = get(y, v);
	//~ for(auto x : a) cout<<x<<" ";
	//~ cout<<"\n";
	//~ for(auto x : b) cout<<x<<" ";
	//~ cout<<"\n";
	//~ 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;
	auto lx = a.begin(), rx = b.begin();
	int last = -1e9, f = -1, res = 1e9;
	while(lx != a.end() || rx != b.end()){
		if(f == 0 && rx != b.end()) res = min(res, *rx - last);
		if(f == 1 && lx != a.end()) res = min(res, *lx - last);
		if(lx != a.end() && rx != b.end()){
			if(*lx <= *rx) last = *lx, f = 0, lx++;
			else last = *rx, f = 1, rx++;
		} else break;
	}
	
	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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7248 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 6 ms 7504 KB Output is correct
3 Correct 5 ms 7504 KB Output is correct
4 Correct 18 ms 8368 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 33920 KB Output is correct
2 Correct 393 ms 34004 KB Output is correct
3 Correct 341 ms 18080 KB Output is correct
4 Correct 1955 ms 77096 KB Output is correct
5 Correct 629 ms 33040 KB Output is correct
6 Execution timed out 3007 ms 109968 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 34012 KB Output is correct
2 Correct 2044 ms 112080 KB Output is correct
3 Correct 1367 ms 67728 KB Output is correct
4 Correct 2294 ms 109540 KB Output is correct
5 Correct 515 ms 38616 KB Output is correct
6 Correct 2433 ms 109636 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9040 KB Output is correct
2 Correct 149 ms 7888 KB Output is correct
3 Correct 250 ms 8016 KB Output is correct
4 Correct 938 ms 10264 KB Output is correct
5 Correct 875 ms 10044 KB Output is correct
6 Correct 149 ms 8144 KB Output is correct
7 Correct 735 ms 9240 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7248 KB Output is correct
2 Correct 6 ms 7504 KB Output is correct
3 Correct 6 ms 7504 KB Output is correct
4 Correct 5 ms 7504 KB Output is correct
5 Correct 18 ms 8368 KB Output is correct
6 Correct 451 ms 33920 KB Output is correct
7 Correct 393 ms 34004 KB Output is correct
8 Correct 341 ms 18080 KB Output is correct
9 Correct 1955 ms 77096 KB Output is correct
10 Correct 629 ms 33040 KB Output is correct
11 Execution timed out 3007 ms 109968 KB Time limit exceeded
12 Halted 0 ms 0 KB -