Submission #574297

#	Time	Username	Problem	Language	Result	Execution time	Memory
574297		benson1029	Snowball (JOI21_ho_t2)	C++14	100 / 100	143 ms	13868 KiB

Main

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

int n, q;
long long pos[200005];
long long x, sum;
long long lmax, rmax;
vector< pair<long long, pair<long long,long long> > > a, b;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> q;
	for(int i=1; i<=n; i++) cin >> pos[i];
	sum = 0;
	lmax = rmax = 0;
	while(q--) {
		cin >> x;
		sum += x;
		if(x < 0 && sum < lmax) {
			lmax = sum;
			a.push_back({-lmax+rmax, {lmax, rmax} });
		} else if(x > 0 && sum > rmax) {
			rmax = sum;
			b.push_back({-lmax+rmax, {lmax, rmax} });
		}
	}
	for(int i=1; i<=n; i++) {
		long long ans = 0;
		if(i == 1) {
			if(a.size() > 0)
				ans += -a[a.size()-1].second.first;
		} else {
			long long gap = pos[i] - pos[i-1];
			int p = lower_bound(a.begin(), a.end(), make_pair(gap, make_pair(0LL,0LL))) - a.begin();
			long long tmp = 0;
			if(p > 0) tmp = max(tmp, -a[p-1].second.first);
			if(p < a.size()) tmp = max(tmp, gap-a[p].second.second);
			ans += tmp;
		}
		
		if(i == n) {
			if(b.size() > 0)
				ans += b[b.size()-1].second.second;
		} else {
			long long gap = pos[i+1] - pos[i];
			int p = lower_bound(b.begin(), b.end(), make_pair(gap, make_pair(0LL,0LL))) - b.begin();
			long long tmp = 0;
			if(p > 0) tmp = max(tmp, b[p-1].second.second);
			if(p < b.size()) tmp = max(tmp, gap+b[p].second.first);
			ans += tmp;
		}
		cout << ans << "\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if(p < a.size()) tmp = max(tmp, gap-a[p].second.second);
      |       ~~^~~~~~~~~~
Main.cpp:49:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    if(p < b.size()) tmp = max(tmp, gap+b[p].second.first);
      |       ~~^~~~~~~~~~

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