Submission #391284

#	Time	Username	Problem	Language	Result	Execution time	Memory
391284		keta_tsimakuridze	Snowball (JOI21_ho_t2)	C++14	100 / 100	497 ms	23116 KiB

Main

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,a[N],n,m,ans[N];
set<pair<int,int> > s;
 main(){
	// t=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(i-1) s.insert({-a[i]+a[i-1],i-1});
	}
	int cur = 0, mxR = 0, mxL = 0;
	for(int i=1;i<=m;i++){
		int w;
		cin >> w;
		cur+=w; //cout<<mxL<<" "<<mxR<<endl;
		if(mxR < cur){
			mxR = cur ; 
			while(s.upper_bound({mxL-mxR,0})!=s.end()){
				int c = (*s.upper_bound({mxL-mxR,0})).s;
		//		cout<<"++"<<c<<" "<<a[c+1]-a[c]+mxL<<endl;
				s.erase(s.upper_bound({mxL-mxR,0}));
				ans[c+1] += -mxL;
				ans[c] += a[c+1]-a[c]+mxL;
			}
		}
		if(mxL > cur) {
			mxL = cur ; 
			while(s.upper_bound({mxL-mxR,0})!=s.end()){
				int c = (*s.upper_bound({mxL-mxR,0})).s;
			//	cout<<"++"<<c<<" " <<mxR<<endl;
				s.erase(s.upper_bound({mxL-mxR,0}));
				ans[c] += mxR;
				ans[c+1] += a[c+1]-a[c]-mxR;
			}			
		}
	}
	ans[1]-=mxL;
	ans[n]+=mxR;
	while(s.size()){
		int c = (*s.begin()).s;
		ans[c] += mxR;
		ans[c+1] += -mxL;
		s.erase(*s.begin());
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
		
}

Compilation message (stderr)

Main.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 |  main(){
      |       ^

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