Submission #792540

#	Time	Username	Problem	Language	Result	Execution time	Memory
792540		ymm	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	1408 ms	170296 KiB

potion

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 100'010;
const int S = 1000;
vector<pair<int,int>> T[N];
vector<tuple<int,int,int>> Ah[(1<<27)/24];
int nxt = 0;
set<pii> A[N];
int h[N];
int n;

void init(int N, int D, int H[]) {
	n = N;
	Loop (i,0,n) {
		h[i] = H[i];
		T[i].push_back({0, nxt++});
	}
}

void flush(int i, int t, bool nw)
{
	for (auto [x, y] : A[i])
		Ah[T[i].back().second].push_back({h[x], y, t});
	if (nw)
		T[i].push_back({t, nxt++});
}

void up(int i, int j, int t)
{
	auto it = A[i].lower_bound(pii{j, 0});
	if (it == A[i].end() || it->first != j) {
		A[i].insert({j, t});
	} else {
		Ah[T[i].back().second].push_back({h[j], it->second, t});
		A[i].erase(it);
	}
	//if (A[i].size() + A[T[i].back().second].size() > S)
	//	flush(i, t, 1);
}

void curseChanges(int U, int A[], int B[]) {
	Loop (i,0,U) {
		up(A[i], B[i], i+1);
		up(B[i], A[i], i+1);
	}
	Loop (i,0,n)
		flush(i, U+1, 0);
	Loop (i,0,nxt) {
		sort(Ah[i].begin(), Ah[i].end());
		//cout << i << ":\n";
		//for (auto [h, l, r] : Ah[i])
		//	cout << h << ' ' << l << ' ' << r << '\n';
		//cout << '\n';
	}
}

vector<tuple<int,int,int>> &get_vec(int x, int t)
{
	auto it = --upper_bound(T[x].begin(), T[x].end(), pii{t, INT_MAX});
	return Ah[it->second];
}

int solve(const vector<tuple<int,int,int>> &a, const vector<tuple<int,int,int>> &b, int t) {
	int ans = 1e9;
	int p0 = 0, p1 = 0;
	while (p0 < a.size() && p1 < b.size()) {
		auto [h1, l1, r1] = a[p0];
		auto [h2, l2, r2] = b[p1];
		if (!(l1 <= t && t < r1)) {
			++p0;
			continue;
		}
		if (!(l2 <= t && t < r2)) {
			++p1;
			continue;
		}
		ans = min(ans, abs(h2 - h1));
		(h1 < h2? p0: p1)++;
	}
	return ans;
}

int question(int x, int y, int v) {
	return solve(get_vec(x, v), get_vec(y, v), v);
}

Compilation message (stderr)

potion.cpp: In function 'int solve(const std::vector<std::tuple<int, int, int> >&, const std::vector<std::tuple<int, int, int> >&, int)':
potion.cpp:70:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  while (p0 < a.size() && p1 < b.size()) {
      |         ~~~^~~~~~~~~~
potion.cpp:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  while (p0 < a.size() && p1 < b.size()) {
      |                          ~~~^~~~~~~~~~

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