Submission #604431

#	Time	Username	Problem	Language	Result	Execution time	Memory
604431		chirathnirodha	Snowball (JOI21_ho_t2)	C++17	100 / 100	117 ms	15468 KiB

Main

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
void solve(){
    io();

	ll n,m;cin>>n>>m;
	ll x[n];
	for(int i=0;i<n;i++){
		cin>>x[i];
		x[i]+=10000000000000;
	}
	ll cur=0;
	ll prmax[m],prmin[m];
	memset(prmax,0,sizeof(prmax));memset(prmin,0,sizeof(prmin));
	vector<ll> v;
	for(int i=0;i<m;i++){
		ll tt;cin>>tt;cur+=tt;
		prmax[i]=max(prmax[i],cur);
		if(i>0)prmax[i]=max(prmax[i],prmax[i-1]);
		prmin[i]=min(prmin[i],cur);
		if(i>0)prmin[i]=min(prmin[i],prmin[i-1]);
		v.PB(prmax[i]-prmin[i]);
	}
	ll w[n];memset(w,0,sizeof(w));
	w[0]+=-prmin[m-1];
	w[n-1]+=prmax[m-1];
	for(int i=0;i<n-1;i++){
		ll dif=x[i+1]-x[i];
		auto lo=lower_bound(v.begin(),v.end(),dif);
		int ind;
		if(lo==v.end() || *lo==dif){
			if(lo==v.end())lo--;
			ind=lo-v.begin();
			w[i]+=prmax[ind];
			w[i+1]+=-prmin[ind];
			continue;
		}
		ind=lo-v.begin();
		if(ind==0){
			w[i]+=min(dif,prmax[ind]);
			w[i+1]+=min(dif,-prmin[ind]);
		}
		else{
			if(prmin[ind]==prmin[ind-1]){
				w[i+1]+=-prmin[ind];
				w[i]+=dif+prmin[ind];
			}
			else{
				w[i]+=prmax[ind];
				w[i+1]+=dif-prmax[ind];
			}
		}
	}
	for(int i=0;i<n;i++)cout<<w[i]<<" ";cout<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:73:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   73 |  for(int i=0;i<n;i++)cout<<w[i]<<" ";cout<<endl;
      |  ^~~
Main.cpp:73:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   73 |  for(int i=0;i<n;i++)cout<<w[i]<<" ";cout<<endl;
      |                                      ^~~~

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