Submission #589105

#	Time	Username	Problem	Language	Result	Execution time	Memory
589105		pooyashams	The Potion of Great Power (CEOI20_potion)	C++14	18 / 100	165 ms	24580 KiB

potion

#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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30