oj.uz

Submission #744733

# Submission time Handle Problem Language Result Execution time Memory
744733 2023-05-19T04:25:51 Z pavement Bitaro's travel (JOI23_travel) C++17
0 / 100
 233 ms 47136 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define int long long

using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int N, Q, X[200005], Y[200005], Z[200005];

struct node0 {
	node0 *left, *right;
	int S, E, val;
	node0(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			val = Z[S];
			return;
		}
		int M = (S + E) >> 1;
		left = new node0(S, M);
		right = new node0(M + 1, E);
		val = max(left->val, right->val);
	}
	int qry(int p, int v) {
		if (p < S) return 0;
		if (E <= p) {
			if (val < v) return 0;
			if (S == E) return S;
			if (right->val >= v) return right->qry(p, v);
			else return left->qry(p, v);
		}
		auto t = right->qry(p, v);
		if (t) return t;
		return left->qry(p, v);
	}
} *root0;

struct node1 {
	node1 *left, *right;
	int S, E, val;
	node1(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			val = Y[S];
			return;
		}
		int M = (S + E) >> 1;
		left = new node1(S, M);
		right = new node1(M + 1, E);
		val = max(left->val, right->val);
	}
	int qry(int p, int v) {
		if (p > E) return N + 1;
		if (p <= S) {
			if (val < v) return N + 1;
			if (S == E) return S;
			if (left->val >= v) return left->qry(p, v);
			else return right->qry(p, v);
		}
		auto t = left->qry(p, v);
		if (t != N + 1) return t;
		return right->qry(p, v);
	}
} *root1;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> X[i];
	}
	for (int i = 1; i <= N; i++) {
		Y[i] = X[i] - 2 * X[i - 1];
		Z[i] = 2 * X[i + 1] - X[i];
		//~ cout << Z[i] << ' ';
	}
	//~ cout << '\n';
	root0 = new node0(1, N);
	root1 = new node1(1, N);
	cin >> Q;
	for (int S; Q--; ) {
		cin >> S;
		int cur = 0;
		int pos = lower_bound(X + 1, X + 1 + N, S) - X;
		int x = (int)-1e16, y = (int)1e16;
		if (pos <= N) {
			y = X[pos];
		}
		if (pos > 1) {
			x = X[pos - 1];
		}
		cur += min(S - x, y - S);
		if (S - x <= y - S) {
			S = pos - 1;
		} else {
			S = pos;
		}
		int l = S, r = S;
		//~ cout << "@ " << S << '\n';
		while (l > 1 || r < N) {
			// decide which direction
			int x = (l == 1 ? (int)1e16 : llabs(X[S] - X[l - 1]));
			int y = (r == N ? (int)1e16 : llabs(X[S] - X[r + 1]));
			if (x <= y) {
				// left
				// find maximum j < l such that
				// Z[j] >= y + X[S] + 1
				//~ int j = root[0]->qry(1, l - 1, y + X[S] + 1) + 1;
				int j = root0->qry(l - 1, y + X[S] + 1) + 1;
				//~ cout << "QQ " << y + X[S] << '\n';
				//~ cout << "GOT " << j << '\n';
				// l --> j
				cur += X[S] - X[j];
				l = S = j;
			} else {
				// right
				// find minimum j > r such that
				// Y[j] >= x - X[S]
				//~ int j = root[1]->qry(r + 1, N, x - X[S]) - 1;
				int j = root1->qry(N, x - X[S]) - 1;
				// r --> j
				cur += X[j] - X[S];
				r = S = j;
			}
			//~ cout << "@ " << S << ' ' << l << ' ' << r << ' ' << cur << '\n';
		}
		cout << cur << '\n';
	}
}

Compilation message

travel.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 230 ms 44696 KB Output is correct
8 Correct 220 ms 46312 KB Output is correct
9 Correct 220 ms 46032 KB Output is correct
10 Correct 217 ms 46120 KB Output is correct
11 Correct 224 ms 46288 KB Output is correct
12 Correct 233 ms 46272 KB Output is correct
13 Correct 39 ms 3968 KB Output is correct
14 Correct 31 ms 1356 KB Output is correct
15 Incorrect 183 ms 47136 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Halted 0 ms 0 KB -