Submission #589135

#	Time	Username	Problem	Language	Result	Execution time	Memory
589135		Arnch	The Potion of Great Power (CEOI20_potion)	C++17	18 / 100	423 ms	215960 KiB

potion

#include<bits/stdc++.h>
using namespace std;

#define mak make_pair
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

const int N = 1e3 + 10, maxn = 1e6 + 10;

int n, d, h[maxn], a[maxn], b[maxn];
map<pair<int, int>, int> mp;
vector<pair<int, int> > vc[maxn][2];
vector<int> mn[maxn][2];

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[]) {
	for(int i = 1; i <= U; i++) {
		a[i] = A[i - 1], b[i] = B[i - 1];
		if(a[i] > b[i]) swap(a[i], b[i]);
	}

	for(int i = 1; i <= U; i++) {
		if(mp[mak(a[i], b[i])] == 0) {
			mp[mak(a[i], b[i])] = i;
		} else {
			vc[a[i]][h[b[i]]].push_back({i - 1, mp[mak(a[i], b[i])]});
			vc[b[i]][h[a[i]]].push_back({i - 1, mp[mak(a[i], b[i])]});
			mp.erase(mak(a[i], b[i]));
		}
	}

	for(auto i : mp) {
		vc[i.first.first][h[i.first.second]].push_back({U, i.second});
		vc[i.first.second][h[i.first.first]].push_back({U, i.second});
	}
	mp.clear();

	for(int i = 0; i < n; i++) sort(All(vc[i][0])), sort(All(vc[i][1]));
	for(int i = 0; i < n; i++) {
		int cnt = 1e9;
		for(int j = 0; j < Sz(vc[i][0]); j++) mn[i][0].push_back(cnt);
		for(int j = Sz(vc[i][0]) - 1; j >= 0; j--) {
			cnt = min(cnt, vc[i][0][j].second);
			mn[i][0][j] = cnt;
		}
		
		cnt = 1e9;
		for(int j = 0; j < Sz(vc[i][1]); j++) mn[i][1].push_back(cnt);
		for(int j = Sz(vc[i][1]) - 1; j >= 0; j--) {
			cnt = min(cnt, vc[i][1][j].second);
			mn[i][1][j] = cnt;
		}
	}
}

int question(int x, int y, int v) {
	int ans = 1e9;

	pair<bool, bool> p1, p2;
	p1 = mak(0, 0), p2 = p1;

	int ind = lower_bound(All(vc[x][0]), mak(v, 0)) - vc[x][0].begin();
	if(ind < Sz(vc[x][0]) && mn[x][0][ind] <= v) {
		p1.first = 1;		
	}
	
	ind = lower_bound(All(vc[x][1]), mak(v, 0)) - vc[x][1].begin();
	if(ind < Sz(vc[x][1]) && mn[x][1][ind] <= v) {
		p1.second = 1;	
	}

	ind = lower_bound(All(vc[y][0]), mak(v, 0)) - vc[y][0].begin();
	if(ind < Sz(vc[y][0]) && mn[y][0][ind] <= v) {
		p2.first = 1;		
	}
	
	ind = lower_bound(All(vc[y][1]), mak(v, 0)) - vc[y][1].begin();
	if(ind < Sz(vc[y][1]) && mn[y][1][ind] <= v) {
		p2.second = 1;		
	}

	if(p1.first == p2.first && p1.first == 1) return 0;
	if(p1.second == p2.second && p1.second == 1) return 0;

	if(p1.first == p2.second && p1.first == 1) return 1;
	if(p1.second == p2.first && p1.second == 1) return 1;

	return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30