oj.uz

Submission #953682

# Submission time Handle Problem Language Result Execution time Memory
953682 2024-03-26T12:44:50 Z lovrot Bitaro's travel (JOI23_travel) C++17
100 / 100
 205 ms 38532 KB 
#include <cstdio> 
#include <vector> 

#define PB push_back

using namespace std; 

typedef long long ll;

const int LOG = 35;
const int N = 2e5 + 10;

int n;
ll X[N]; 

vector<int> L[N], R[N]; 

ll solve(int l, int r, bool flag) {
	if(l == 0 && r == n - 1) return 0;
	ll ret = 0; 
	
//	printf("%d %d %d \n", l, r, flag);

	if(flag == 0) {
		if(r == n - 1) return X[l] - X[0];
		if(l == 0) return X[r + 1] - X[0] + solve(0, r + 1, 1);

		int nxt = -1;
		for(int i = (int) L[r + 1].size() - 1; i >= 0; --i)
			if(L[r + 1][i] < l) {
				nxt = L[r + 1][i];
				break;
			}
		return nxt == -1 ? X[l] - X[0] + solve(0, r, 0) : X[l] + X[r + 1] - 2 * X[nxt + 1] + solve(nxt + 1, r + 1, 1);
	} else {
		if(l == 0) return X[n - 1] - X[r]; 
		if(r == n - 1) return X[n - 1] - X[l - 1] + solve(l - 1, n - 1, 0);

		int nxt = -1;
		for(int i = (int) R[l - 1].size() - 1; i >= 0; --i)
			if(R[l - 1][i] > r) {
				nxt = R[l - 1][i];
				break;
			}
		return nxt == -1 ? X[n - 1] - X[r] + solve(l, n - 1, 1) : 2 * X[nxt - 1] - X[r] - X[l - 1] + solve(l - 1, nxt - 1, 0);
	}
	return 0;
}

int main() {
	scanf("%d", &n);

	for(int i = 0; i < n; ++i) {
		scanf("%lld", X + i); 

		if(i) {
			for(int x : L[i - 1])
				if(X[x + 1] - X[x] > X[i] - X[x + 1]) L[i].PB(x);
			L[i].PB(i - 1);
		}
	}

	for(int i = n - 2; i >= 0; --i) {
		for(int x : R[i + 1])
			if(X[x] - X[x - 1] >= X[x - 1] - X[i]) R[i].PB(x); 
		R[i].PB(i + 1);
	}

	int q; scanf("%d", &q);
	for(; q--; ) {
		ll x; scanf("%lld", &x); 

		int lo = -1, hi = n;
		for(; hi - lo > 1; ) {
			int mi = (lo + hi) / 2;
			if(X[mi] <= x) lo = mi;
			else hi = mi;
		}
	
//		printf("%d %d\n", lo, hi);
		if(lo == -1) printf("%lld\n", X[0] - x + solve(0, 0, 1));
		else if(hi == n) printf("%lld\n", x - X[n - 1] + solve(n - 1, n - 1, 0));
		else printf("%lld\n", X[hi] - x >= x - X[lo] ? solve(lo, lo, 0) + x - X[lo] : solve(hi, hi, 1) + X[hi] - x);
	}
	return 0;
}

Compilation message

travel.cpp: In function 'll solve(int, int, bool)':
travel.cpp:20:5: warning: unused variable 'ret' [-Wunused-variable]
   20 |  ll ret = 0;
      |     ^~~
travel.cpp: In function 'int main()':
travel.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
travel.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%lld", X + i);
      |   ~~~~~^~~~~~~~~~~~~~~
travel.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
travel.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   ll x; scanf("%lld", &x);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 4 ms 9816 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 3 ms 9820 KB Output is correct
16 Correct 3 ms 9820 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 4 ms 9816 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 3 ms 9820 KB Output is correct
16 Correct 3 ms 9820 KB Output is correct
17 Correct 68 ms 26968 KB Output is correct
18 Correct 68 ms 26964 KB Output is correct
19 Correct 66 ms 26964 KB Output is correct
20 Correct 68 ms 26712 KB Output is correct
21 Correct 67 ms 27072 KB Output is correct
22 Correct 69 ms 26820 KB Output is correct
23 Correct 66 ms 26708 KB Output is correct
24 Correct 55 ms 25676 KB Output is correct
25 Correct 70 ms 25788 KB Output is correct
26 Correct 55 ms 25684 KB Output is correct
27 Correct 59 ms 25700 KB Output is correct
28 Correct 55 ms 25596 KB Output is correct
29 Correct 83 ms 34388 KB Output is correct
30 Correct 89 ms 34380 KB Output is correct
31 Correct 85 ms 34428 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9836 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9792 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 125 ms 27580 KB Output is correct
8 Correct 130 ms 27728 KB Output is correct
9 Correct 126 ms 27588 KB Output is correct
10 Correct 124 ms 27816 KB Output is correct
11 Correct 127 ms 27724 KB Output is correct
12 Correct 141 ms 28008 KB Output is correct
13 Correct 43 ms 13904 KB Output is correct
14 Correct 35 ms 10840 KB Output is correct
15 Correct 137 ms 28892 KB Output is correct
16 Correct 147 ms 28836 KB Output is correct
17 Correct 152 ms 28752 KB Output is correct
18 Correct 44 ms 13652 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 4 ms 9816 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 4 ms 9816 KB Output is correct
9 Correct 3 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 3 ms 9820 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 3 ms 9820 KB Output is correct
15 Correct 3 ms 9820 KB Output is correct
16 Correct 3 ms 9820 KB Output is correct
17 Correct 68 ms 26968 KB Output is correct
18 Correct 68 ms 26964 KB Output is correct
19 Correct 66 ms 26964 KB Output is correct
20 Correct 68 ms 26712 KB Output is correct
21 Correct 67 ms 27072 KB Output is correct
22 Correct 69 ms 26820 KB Output is correct
23 Correct 66 ms 26708 KB Output is correct
24 Correct 55 ms 25676 KB Output is correct
25 Correct 70 ms 25788 KB Output is correct
26 Correct 55 ms 25684 KB Output is correct
27 Correct 59 ms 25700 KB Output is correct
28 Correct 55 ms 25596 KB Output is correct
29 Correct 83 ms 34388 KB Output is correct
30 Correct 89 ms 34380 KB Output is correct
31 Correct 85 ms 34428 KB Output is correct
32 Correct 2 ms 9816 KB Output is correct
33 Correct 2 ms 9820 KB Output is correct
34 Correct 2 ms 9836 KB Output is correct
35 Correct 2 ms 9820 KB Output is correct
36 Correct 3 ms 9792 KB Output is correct
37 Correct 2 ms 9820 KB Output is correct
38 Correct 125 ms 27580 KB Output is correct
39 Correct 130 ms 27728 KB Output is correct
40 Correct 126 ms 27588 KB Output is correct
41 Correct 124 ms 27816 KB Output is correct
42 Correct 127 ms 27724 KB Output is correct
43 Correct 141 ms 28008 KB Output is correct
44 Correct 43 ms 13904 KB Output is correct
45 Correct 35 ms 10840 KB Output is correct
46 Correct 137 ms 28892 KB Output is correct
47 Correct 147 ms 28836 KB Output is correct
48 Correct 152 ms 28752 KB Output is correct
49 Correct 44 ms 13652 KB Output is correct
50 Correct 205 ms 31020 KB Output is correct
51 Correct 188 ms 31116 KB Output is correct
52 Correct 185 ms 31216 KB Output is correct
53 Correct 172 ms 29748 KB Output is correct
54 Correct 180 ms 29780 KB Output is correct
55 Correct 181 ms 29780 KB Output is correct
56 Correct 143 ms 38532 KB Output is correct
57 Correct 145 ms 38484 KB Output is correct
58 Correct 141 ms 38436 KB Output is correct