oj.uz

Submission #589105

# Submission time Handle Problem Language Result Execution time Memory
589105 2022-07-04T09:25:46 Z pooyashams The Potion of Great Power (CEOI20_potion) C++14
18 / 100
 165 ms 24580 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 inf = 1e9;

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

vector<pii> qrs[maxn];
vector<pii> fcnt[maxn];

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

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];
		qrs[A[i]].push_back( pii(i, B[i]) );
		qrs[B[i]].push_back( pii(i, A[i]) );
	}
	for(int i = 0; i < n; i++)
	{
		set<int> curs;
		vector<int>x = {0, 0};
		for(pii p: qrs[i])
		{
			int y = p.second;
			if(curs.count(y))
			{
				x[H[y]]--;
				curs.erase(y);
			}
			else
			{
				x[H[y]]++;
				curs.insert(y);
			}
			fcnt[i].push_back(pii(x[0], x[1]));
		}
	}
}

int question(int x, int y, int v)
{
	v--;
	int idx = upper_bound(qrs[x].begin(), qrs[x].end(), pii(v, inf)) - qrs[x].begin();
	int idy = upper_bound(qrs[y].begin(), qrs[y].end(), pii(v, inf)) - qrs[y].begin();
	pii px(0, 0);
	pii py(0, 0);
	if(idx > 0)
		px = fcnt[x][idx-1];
	if(idy > 0)
		py = fcnt[y][idy-1];
	pii p0(0, 0);
	if(px == p0 or py == p0)
		return inf;
	//px.first = bool(px.first);
	//px.second = bool(px.second);
	//py.first = bool(py.first);
	//py.second = bool(py.second);
	if( (px.first and py.first) or (px.second and py.second) )
		return 0;
	return 1;
}

Subtask #1
0 / 0.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9824 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 24536 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 24580 KB Output is correct
2 Correct 140 ms 21904 KB Output is correct
3 Correct 161 ms 23492 KB Output is correct
4 Correct 161 ms 23412 KB Output is correct
5 Correct 148 ms 24520 KB Output is correct
6 Correct 165 ms 23496 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 10592 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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