Submission #522247

#	Time	Username	Problem	Language	Result	Execution time	Memory
522247		AdamGS	Snowball (JOI21_ho_t2)	C++17	100 / 100	102 ms	15324 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
ll T[LIM], W[LIM], mi[LIM], ma[LIM], ans[LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q;
	cin >> n >> q;
	rep(i, n) cin >> T[i];
	ll sum=0;
	rep(i, q) {
		cin >> W[i];
		sum+=W[i];
		mi[i+1]=min(mi[i], sum);
		ma[i+1]=max(ma[i], sum);
	}
	ans[0]-=mi[q];
	ans[n-1]+=ma[q];
	rep(i, n-1) {
		ll x=T[i+1]-T[i];
		int p=0, k=q;
		while(p<k) {
			int sr=(p+k+1)/2;
			if(ma[sr]-mi[sr]<=x) p=sr; else k=sr-1;
		}
		ans[i]+=ma[p];
		ans[i+1]-=mi[p];
		x-=ma[p]-mi[p];
		if(p<q) {
			if(W[p]>=0) ans[i]+=x;
			else ans[i+1]+=x;
		}
	}
	rep(i, n) cout << ans[i] << '\n';
}

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