oj.uz

Submission #578491

# Submission time Handle Problem Language Result Execution time Memory
578491 2022-06-17T04:51:15 Z amunduzbaev The Potion of Great Power (CEOI20_potion) C++17
52 / 100
 3000 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ar array
#define ff first
#define ss second
const int N = 1e5 + 5;
const int C = 15;
vector<pair<int, int>> edges[N];
vector<set<pair<int, int>>> vals[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[]) {
	for(int i=0;i<U;i++){
		edges[A[i]].push_back({i + 1, B[i]});
		edges[B[i]].push_back({i + 1, A[i]});
	}
	
	for(int i=0;i<n;i++){
		set<pair<int, int>> ss;
		int v = 0;
		for(int j=0;j<(int)edges[i].size();j++){
			if(j == v){ v += C;
				vals[i].push_back(ss);
			}

			if(ss.count({h[edges[i][j].ss], edges[i][j].ss})){
				ss.erase({h[edges[i][j].ss], edges[i][j].ss});
			} else {
				ss.insert({h[edges[i][j].ss], edges[i][j].ss});
			}
		}
	}
}

void get(int a, int t, set<pair<int, int>>& res){
	int j = lower_bound(edges[a].begin(), edges[a].end(), make_pair(t + 1, -1)) - edges[a].begin();
	if(!j) return;
	j--;
	
	res = vals[a][j/C];
	for(int k=(j/C) * C;k<(int)edges[a].size() && edges[a][k].ff<=t;k++){
		if(res.count({h[edges[a][k].ss], edges[a][k].ss})){
			res.erase({h[edges[a][k].ss], edges[a][k].ss});
		} else {
			res.insert({h[edges[a][k].ss], edges[a][k].ss});
		}
	}
	
	return;
}

set<pair<int, int>> a, b;
int question(int x, int y, int v) {
	a.clear(), b.clear();
	get(x, v, a), get(y, v, b);
	
	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).ff - last);
		if(f == 1 && lx != a.end()) res = min(res, (*lx).ff - last);
		if(lx != a.end() && rx != b.end()){
			if(*lx <= *rx) last = (*lx).ff, f = 0, lx++;
			else last = (*rx).ff, 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 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 19 ms 5980 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 19392 KB Output is correct
2 Correct 198 ms 19488 KB Output is correct
3 Correct 275 ms 24308 KB Output is correct
4 Correct 1684 ms 169028 KB Output is correct
5 Correct 531 ms 37680 KB Output is correct
6 Correct 3000 ms 242652 KB Output is correct
7 Correct 629 ms 41408 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 19508 KB Output is correct
2 Runtime error 360 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5968 KB Output is correct
2 Correct 140 ms 5968 KB Output is correct
3 Correct 219 ms 5968 KB Output is correct
4 Correct 890 ms 10064 KB Output is correct
5 Correct 825 ms 9040 KB Output is correct
6 Correct 149 ms 5968 KB Output is correct
7 Correct 738 ms 9104 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 19 ms 5980 KB Output is correct
6 Correct 212 ms 19392 KB Output is correct
7 Correct 198 ms 19488 KB Output is correct
8 Correct 275 ms 24308 KB Output is correct
9 Correct 1684 ms 169028 KB Output is correct
10 Correct 531 ms 37680 KB Output is correct
11 Correct 3000 ms 242652 KB Output is correct
12 Correct 629 ms 41408 KB Output is correct
13 Correct 194 ms 19508 KB Output is correct
14 Runtime error 360 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -