oj.uz

Submission #922823

# Submission time Handle Problem Language Result Execution time Memory
922823 2024-02-06T07:14:46 Z penguin133 Snowball (JOI21_ho_t2) C++17
100 / 100
 872 ms 12548 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

vector <int> pos, neg;
int n, q, X[200005];

void solve(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++)cin >> X[i];
	X[n + 1] = 1e18;
	int cur = 0, mx = 0, mn = 0;
	for(int i = 1; i <= q; i++){
		int x; cin >> x;
		cur += x;
		mx = max(mx, cur);
		mn = min(mn, cur);
		pos.push_back(mx); neg.push_back(-mn);
	}
	int prv = X[1] + mn;
	for(int i = 1; i <= n; i++){
		int lp = max(prv, X[i] + mn);
		int lo = X[i], hi = X[i + 1], ans = lo;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			int tmp = lower_bound(pos.begin(), pos.end(), mid - X[i]) - pos.begin();
			int tmp2 = lower_bound(neg.begin(), neg.end(), X[i + 1] - mid + 1) - neg.begin();
			if(tmp < tmp2)ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		//cout << ans << ' ' << lp << ' ';
		cout << ans - lp << '\n';
		prv = ans;
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

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

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 472 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 476 KB Output is correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 472 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 476 KB Output is correct
20 Correct 25 ms 5812 KB Output is correct
21 Correct 25 ms 5732 KB Output is correct
22 Correct 20 ms 5556 KB Output is correct
23 Correct 32 ms 5300 KB Output is correct
24 Correct 104 ms 5716 KB Output is correct
25 Correct 837 ms 10680 KB Output is correct
26 Correct 857 ms 10420 KB Output is correct
27 Correct 792 ms 10104 KB Output is correct
28 Correct 769 ms 10564 KB Output is correct
29 Correct 720 ms 9872 KB Output is correct
30 Correct 437 ms 9168 KB Output is correct
31 Correct 74 ms 8568 KB Output is correct
32 Correct 65 ms 8784 KB Output is correct
33 Correct 67 ms 1692 KB Output is correct
34 Correct 778 ms 11052 KB Output is correct
35 Correct 779 ms 10408 KB Output is correct
36 Correct 872 ms 10784 KB Output is correct
37 Correct 782 ms 10212 KB Output is correct
38 Correct 780 ms 10276 KB Output is correct
39 Correct 779 ms 10352 KB Output is correct
40 Correct 224 ms 10240 KB Output is correct
41 Correct 24 ms 6792 KB Output is correct
42 Correct 146 ms 8708 KB Output is correct
43 Correct 171 ms 12336 KB Output is correct
44 Correct 21 ms 6324 KB Output is correct
45 Correct 309 ms 10400 KB Output is correct
46 Correct 207 ms 12312 KB Output is correct
47 Correct 197 ms 12464 KB Output is correct
48 Correct 188 ms 12548 KB Output is correct