oj.uz

Submission #792540

# Submission time Handle Problem Language Result Execution time Memory
792540 2023-07-25T06:41:51 Z ymm The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1408 ms 170296 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 138636 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 138760 KB Output is correct
2 Correct 60 ms 138760 KB Output is correct
3 Correct 65 ms 138804 KB Output is correct
4 Correct 73 ms 142680 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 170268 KB Output is correct
2 Correct 318 ms 170296 KB Output is correct
3 Correct 459 ms 147116 KB Output is correct
4 Correct 446 ms 156380 KB Output is correct
5 Correct 364 ms 166520 KB Output is correct
6 Correct 919 ms 154432 KB Output is correct
7 Correct 381 ms 154264 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 170240 KB Output is correct
2 Correct 590 ms 147792 KB Output is correct
3 Correct 398 ms 154796 KB Output is correct
4 Correct 517 ms 154448 KB Output is correct
5 Correct 325 ms 169696 KB Output is correct
6 Correct 575 ms 154440 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 140380 KB Output is correct
2 Correct 110 ms 139412 KB Output is correct
3 Correct 193 ms 139224 KB Output is correct
4 Correct 287 ms 139928 KB Output is correct
5 Correct 246 ms 140248 KB Output is correct
6 Correct 110 ms 139984 KB Output is correct
7 Correct 553 ms 139396 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 138636 KB Output is correct
2 Correct 59 ms 138760 KB Output is correct
3 Correct 60 ms 138760 KB Output is correct
4 Correct 65 ms 138804 KB Output is correct
5 Correct 73 ms 142680 KB Output is correct
6 Correct 295 ms 170268 KB Output is correct
7 Correct 318 ms 170296 KB Output is correct
8 Correct 459 ms 147116 KB Output is correct
9 Correct 446 ms 156380 KB Output is correct
10 Correct 364 ms 166520 KB Output is correct
11 Correct 919 ms 154432 KB Output is correct
12 Correct 381 ms 154264 KB Output is correct
13 Correct 307 ms 170240 KB Output is correct
14 Correct 590 ms 147792 KB Output is correct
15 Correct 398 ms 154796 KB Output is correct
16 Correct 517 ms 154448 KB Output is correct
17 Correct 325 ms 169696 KB Output is correct
18 Correct 575 ms 154440 KB Output is correct
19 Correct 95 ms 140380 KB Output is correct
20 Correct 110 ms 139412 KB Output is correct
21 Correct 193 ms 139224 KB Output is correct
22 Correct 287 ms 139928 KB Output is correct
23 Correct 246 ms 140248 KB Output is correct
24 Correct 110 ms 139984 KB Output is correct
25 Correct 553 ms 139396 KB Output is correct
26 Correct 410 ms 147844 KB Output is correct
27 Correct 568 ms 154796 KB Output is correct
28 Correct 530 ms 163660 KB Output is correct
29 Correct 454 ms 156416 KB Output is correct
30 Correct 913 ms 154244 KB Output is correct
31 Correct 1408 ms 147664 KB Output is correct
32 Correct 843 ms 154296 KB Output is correct