Submission #943364

#	Time	Username	Problem	Language	Result	Execution time	Memory
943364		ErJ	Snowball (JOI21_ho_t2)	C++17	0 / 100	3 ms	856 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mpp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define mod 1000000007
#define rep(a, b) for(int a = 0; a < (b); a++)
#define rep2(a, b) for(int a = 1; a < (b); a++)
#define inf 10000000000000000

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, q;
	cin >> n >> q;
	vi A(n + 2), B(q);
	A[0] = -inf/10;
	rep(i, n) {
		cin >> A[i + 1];
	}
	A[n + 1] = inf/10;
	rep(i, q) {
		cin >> B[i];
	}
	vi pref(q + 1);
	pref[0] = 0;
	vi MIN(q + 1), MAX(q + 1), C(q + 1);
	MIN[0] = 0;
	MAX[0] = 0;
	C[0] = -inf;
	rep(i, q) {
		pref[i + 1] = pref[i] + B[i];
		MIN[i + 1] = min(MIN[i], pref[i + 1]);
		MAX[i + 1] = max(MAX[i], pref[i + 1]);
		C[i + 1] = abs(MIN[i + 1]) + abs(MAX[i + 1]);
	}
	C.push_back(inf);
	rep(i, n) {
		ll a = A[i + 1];
		ll L = A[i];
		ll R = A[i + 2];
		ll ANS = 0;
		ll l = 0, r = C.size();
		ll ans = -1;
		while (l + 1 < r) {
			ll s = (l + r) / 2;
			if (C[s] < a - L || (C[s] == a - L && C[s + 1] == a - L)) {
				l = s;
			}
			else if (C[s] > a - L) {
				r = s;
			}
			else if (C[s] == a - L && (C[s + 1] > a - L)) {
				ans = s;
				break;
			}
		}
		if (ans == -1) ans = l;
		ll index = ans;
		ANS += abs(MIN[index]);
		if (index + 1 < MIN.size() - 1) {
			if (MIN[index] != MIN[index + 1]) {
				ANS = ANS + (a - L) - abs(MAX[index]) - abs(MIN[index]);
			}
		}
		l = 0; r = C.size();
		ans = -1;
		while (l + 1 < r) {
			ll s = (l + r) / 2;
			if (C[s] < R - a || (C[s] == R - a && C[s + 1] == R - a)) {
				l = s;
			}
			else if (C[s] > R - a) {
				r = s;
			}
			else if (C[s] == R - a && (C[s + 1] > R - a)) {
				ans = s;
				break;
			}
		}
		if (ans == -1) ans = l;
		index = ans;
		ANS += abs(MAX[index]);
		if (index + 1 <= MAX.size() - 1) {
			if (MAX[index] != MAX[index + 1]) {
				ANS = ANS + (R - a) - abs(MAX[index]) - abs(MIN[index]);
			}
		}
		cout << ANS << endl;
	}


}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if (index + 1 < MIN.size() - 1) {
      |       ~~~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:101:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if (index + 1 <= MAX.size() - 1) {
      |       ~~~~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 33
• Subtask 2: 0 / 67