oj.uz

Submission #578087

# Submission time Handle Problem Language Result Execution time Memory
578087 2022-06-16T03:56:27 Z amunduzbaev The Potion of Great Power (CEOI20_potion) C++17
17 / 100
 3000 ms 20792 KB 
#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];
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;
		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;
	//~ 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 : a){
		auto it = b.lower_bound(x);
		if(it != b.end()){
			res = min(res, *it - x);
		} if(it != b.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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct
2 Correct 3 ms 2768 KB Output is correct
3 Correct 3 ms 2692 KB Output is correct
4 Correct 14 ms 3556 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 20792 KB Output is correct
2 Correct 351 ms 20728 KB Output is correct
3 Execution timed out 3022 ms 8740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3536 KB Output is correct
2 Correct 232 ms 3092 KB Output is correct
3 Correct 2118 ms 3052 KB Output is correct
4 Correct 2405 ms 3344 KB Output is correct
5 Correct 2081 ms 3436 KB Output is correct
6 Correct 149 ms 3464 KB Output is correct
7 Execution timed out 3064 ms 3088 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct
2 Correct 3 ms 2640 KB Output is correct
3 Correct 3 ms 2768 KB Output is correct
4 Correct 3 ms 2692 KB Output is correct
5 Correct 14 ms 3556 KB Output is correct
6 Correct 358 ms 20792 KB Output is correct
7 Correct 351 ms 20728 KB Output is correct
8 Execution timed out 3022 ms 8740 KB Time limit exceeded
9 Halted 0 ms 0 KB -