oj.uz

답안 #444367

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444367 2021-07-13T19:07:21 Z aryan12 Snowball (JOI21_ho_t2) C++17
33 / 100
 166 ms 12324 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
vector<int> a, query;
vector<array<int, 2> > newQueries;

int CalcPre(int i) {
	int dist_pre = a[i] - a[i - 1];
	int cur_ans = 0;
	if(newQueries[q][0] - newQueries[q][1] < dist_pre) {
		return -newQueries[q][1];
	}
	int l = 0, r = q;
	int mid, ans = 0;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(newQueries[mid][0] - newQueries[mid][1] < dist_pre) {
			ans = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	mid = ans;
	if(newQueries[mid + 1][1] < newQueries[mid][1]) {
		cur_ans += dist_pre - newQueries[mid + 1][0];
	}
	else {
		cur_ans += -newQueries[mid][1];
	}
	return cur_ans;
}

int CalcSuf(int i) {
	int dist_suf = a[i + 1] - a[i];
	int cur_ans = 0;
	if(newQueries[q][0] - newQueries[q][1] < dist_suf) {
		return newQueries[q][0];
	}
	int l = 0, r = q;
	int mid, ans = 0;
	//cout << "dist_suf = " << dist_suf << "\n";
	while(l <= r) {
		mid = (l + r) >> 1;
		if(newQueries[mid][0] - newQueries[mid][1] < dist_suf) {
			ans = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	mid = ans;
	//cout << "cur_ans = " << cur_ans << "\n";
	//cout << "mid = " << mid << "\n";
	if(newQueries[mid + 1][0] > newQueries[mid][0]) {
		cur_ans += dist_suf + newQueries[mid + 1][1];
	}
	else {
		cur_ans += newQueries[mid][0];
	}
	return cur_ans;
}

void Solve() {
	cin >> n >> q;
	a.resize(n + 1);
	a[0] = -1e15;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	a.push_back(1e15);
	query.resize(q + 1);
	for(int i = 1; i <= q; i++) {
		cin >> query[i];
	}
	int sum = 0, maxx = 0, minx = 0;
	newQueries.resize(q + 1);
	newQueries[0] = {0, 0};
	for(int i = 1; i <= q; i++) {
		sum += query[i];
		maxx = max(maxx, sum);
		minx = min(minx, sum);
		newQueries[i] = {maxx, minx};
		//cout << newQueries[i][0] << " " << newQueries[i][1] << "\n";
	}
	for(int i = 1; i <= n; i++) {
		//int ans1 = CalcPre(i), ans2 = CalcSuf(i);
		//cout << "ans1[" << i << "] = " << ans1 << ", ans2[" << i << "] = " << ans2 << "\n";
		int ans = CalcPre(i) + CalcSuf(i);
		cout << ans << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 328 KB Output is correct

Subtask #2
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 33 ms 7120 KB Output is correct
21 Correct 31 ms 6860 KB Output is correct
22 Correct 32 ms 6744 KB Output is correct
23 Correct 29 ms 6640 KB Output is correct
24 Correct 38 ms 6892 KB Output is correct
25 Correct 143 ms 11824 KB Output is correct
26 Correct 143 ms 11820 KB Output is correct
27 Correct 140 ms 11428 KB Output is correct
28 Correct 147 ms 11608 KB Output is correct
29 Correct 141 ms 11148 KB Output is correct
30 Correct 133 ms 10532 KB Output is correct
31 Correct 100 ms 9940 KB Output is correct
32 Correct 78 ms 10032 KB Output is correct
33 Correct 13 ms 1492 KB Output is correct
34 Correct 166 ms 12324 KB Output is correct
35 Correct 143 ms 11568 KB Output is correct
36 Correct 145 ms 11816 KB Output is correct
37 Correct 150 ms 11628 KB Output is correct
38 Correct 140 ms 11428 KB Output is correct
39 Correct 139 ms 11632 KB Output is correct
40 Correct 97 ms 11568 KB Output is correct
41 Incorrect 36 ms 7744 KB Output isn't correct
42 Halted 0 ms 0 KB -