Submission #1363741

#TimeUsernameProblemLanguageResultExecution timeMemory
1363741weedywelonSnowball (JOI21_ho_t2)C++20
100 / 100
46 ms9948 KiB
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const LL MAXN=2e5+5;
LL pref[MAXN], x[MAXN], ans[MAXN];

signed main(){
	FAST;
	LL n,q; cin>>n>>q;
	FR(i,1,n+1) cin>>x[i];
	FR(i,1,q+1){
		cin>>pref[i];
		pref[i]+=pref[i-1];
	}
	
	vector<PLL> v;
	FR(i,1,n) v.push_back(mp(x[i+1]-x[i],i));
	sort(v.begin(),v.end());
	
	int idx=0;
	LL l=0, r=0, tot=0;
	FR(i,1,q+1){
		int rec=0;
		if (pref[i]<0) l=max(l,abs(pref[i]));
		else{
			r=max(r,pref[i]);
			if (r==pref[i]) rec=1;
		}
		
		tot=l+r;
		while (idx<SZ(v) && v[idx].A<=tot){
			LL sz=v[idx].A, lf=v[idx].B, rt=lf+1;
			
			//cout<<lf<<" "<<rt<<": "<<l<<" "<<r<<" "<<sz<<"\n";
			if (rec){
				ans[lf]+=sz-l; //r became big
				ans[rt]+=l;
			}
			else{
				ans[rt]+=sz-r;
				ans[lf]+=r;
			}
			idx++;
		}
		
		//FR(i,1,n+1) cout<<ans[i]<<" ";
		//cout<<"\n-----------\n";
	}
	
	//cout<<"l: "<<l<<" "<<"r: "<<r<<"\n";
	ans[1]+=l;
	ans[n]+=r;
	
	FR(i,idx,SZ(v)){
		LL lf=v[i].B, rt=lf+1;
		ans[lf]+=r;
		ans[rt]+=l;
	}
	
	FR(i,1,n+1) cout<<ans[i]<<"\n";
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...