oj.uz

Submission #589067

# Submission time Handle Problem Language Result Execution time Memory
589067 2022-07-04T09:08:23 Z pooyashams The Potion of Great Power (CEOI20_potion) C++14
17 / 100
 72 ms 7052 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int maxu = 2012;
const int inf = 1e9;

int n, D;
int H[maxn];
int U;
int A[maxu];
int B[maxu];

bool hasfrn[maxn];
int id[maxn];

int wfrn[maxu];
int fcnt = 0;

bool state[2][maxu];

void init(int N, int D, int H[])
{
	::n = N;
	::D = D;
	for(int i = 0; i < N; i++)
		::H[i] = H[i];
	fill(id, id+N, -1);
}

void curseChanges(int U, int A[], int B[])
{
	::U= U;
	for(int i = 0; i < U; i++)
	{
		::A[i] = A[i];
		::B[i] = B[i];
		hasfrn[A[i]] = true;
		hasfrn[B[i]] = true;
	}
	for(int i = 0; i < n; i++)
	{
		if(hasfrn[i])
			wfrn[fcnt++] = i;
	}
	sort(wfrn, wfrn+fcnt, [&](int i, int j){return H[i] < H[j];});
	for(int i = 0; i < fcnt; i++)
		id[wfrn[i]] = i;
}

int cfrs[2][maxu];

int question(int x, int y, int v)
{
	if(!hasfrn[x] and !hasfrn[y])
		return inf;
	memset(state, 0, sizeof(state));
	for(int i = 0; i < v; i++)
	{
		if(A[i] == x)
		{
			state[0][id[B[i]]] ^= 1;
			//cerr << "0 " << id[B[i]] << endl;
		}
		else if(B[i] == x)
		{
			state[0][id[A[i]]] ^= 1;
			//cerr << "0 " << id[A[i]] << endl;
		}
		if(A[i] == y)
		{
			state[1][id[B[i]]] ^= 1;
			//cerr << "1 " << id[B[i]] << endl;
		}
		else if(B[i] == y)
		{
			state[1][id[A[i]]] ^= 1;
			//cerr << "1 " << id[A[i]] << endl;
		}
	}
	int xc = 0;
	int yc = 0;
	for(int i = 0; i < fcnt; i++)
	{
		if(state[0][i])
			cfrs[0][xc++] = wfrn[i];
		if(state[1][i])
			cfrs[1][yc++] = wfrn[i];
	}
	//for(int i = 0; i < xc; i++)
	//	cerr << cfrs[0][i] << " ";
	//cerr << endl;
	//for(int i = 0; i < yc; i++)
	//	cerr << cfrs[1][i] << " ";
	//cerr << endl;
	int p = 0;
	int ans = inf;
	for(int i = 0; i < xc; i++)
	{
		while(p < yc and H[cfrs[1][p]] < H[cfrs[0][i]])
			p++;
		if(p > 0)
			ans = min(ans, abs(H[cfrs[0][i]] - H[cfrs[1][p-1]]) );
		if(p < yc)
			ans = min(ans, abs(H[cfrs[0][i]] - H[cfrs[1][p]]) );
	}
	return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 5 ms 336 KB Output is correct
4 Correct 21 ms 1612 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 6988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 72 ms 7052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 5 ms 336 KB Output is correct
5 Correct 21 ms 1612 KB Output is correct
6 Runtime error 53 ms 6988 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -