oj.uz

Submission #792536

# Submission time Handle Problem Language Result Execution time Memory
792536 2023-07-25T06:35:25 Z ymm The Potion of Great Power (CEOI20_potion) C++17
0 / 100
 365 ms 170372 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 && l2 <= t && t < r2)
			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 63 ms 138568 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 138740 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 304 ms 170260 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 365 ms 170372 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 140464 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 138568 KB Output is correct
2 Incorrect 62 ms 138740 KB Incorrect
3 Halted 0 ms 0 KB -