oj.uz

Submission #578486

# Submission time Handle Problem Language Result Execution time Memory
578486 2022-06-17T04:48:17 Z amunduzbaev The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 89516 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 = 50;
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 3 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 21 ms 6032 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 19460 KB Output is correct
2 Correct 222 ms 19520 KB Output is correct
3 Correct 398 ms 14708 KB Output is correct
4 Correct 1871 ms 57952 KB Output is correct
5 Correct 660 ms 13452 KB Output is correct
6 Execution timed out 3030 ms 85576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 19508 KB Output is correct
2 Correct 2527 ms 89516 KB Output is correct
3 Correct 1563 ms 51716 KB Output is correct
4 Correct 2645 ms 85008 KB Output is correct
5 Correct 385 ms 23420 KB Output is correct
6 Execution timed out 3031 ms 85224 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5968 KB Output is correct
2 Correct 249 ms 5408 KB Output is correct
3 Correct 371 ms 5584 KB Output is correct
4 Correct 1089 ms 7196 KB Output is correct
5 Correct 957 ms 6864 KB Output is correct
6 Correct 179 ms 5308 KB Output is correct
7 Correct 971 ms 6480 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 21 ms 6032 KB Output is correct
6 Correct 206 ms 19460 KB Output is correct
7 Correct 222 ms 19520 KB Output is correct
8 Correct 398 ms 14708 KB Output is correct
9 Correct 1871 ms 57952 KB Output is correct
10 Correct 660 ms 13452 KB Output is correct
11 Execution timed out 3030 ms 85576 KB Time limit exceeded
12 Halted 0 ms 0 KB -