Submission #543302

#	Time	Username	Problem	Language	Result	Execution time	Memory
543302		Aktan	Snowball (JOI21_ho_t2)	C++14	100 / 100	129 ms	10408 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define ft first
#define sc second
const int mod=1e9+7,INF=1e17,N=2e5+10;

int mn[N],mx[N],ans[N];
main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,q;
	cin >> n >> q;
	vector<int> a(n+1),b(q+1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	int cnt=0;
	for(int i=1;i<=q;i++){
		cin >> b[i];
		cnt+=b[i];
		mn[i]=min(mn[i-1],cnt);
		mx[i]=max(mx[i-1],cnt);
	}
	ans[1]+=abs(mn[q]);
    ans[n]+=mx[q];
	for(int i=1;i<n;i++){
		if(a[i]+mx[q]<=a[i+1]+mn[q]){
            ans[i]+=mx[q];
            ans[i+1]+=abs(mn[q]);
        }
		else{
		int l=1,r=q;
		while(l<r){
			int m=(l+r)/2;
			if(a[i]+mx[m]>a[i+1]+mn[m]){
				r=m;
			}
			else{
				l=m+1;
			}
		}
		if(b[l]>0){
                ans[i]+=max(0ll,a[i+1]+mn[l-1]-a[i]);
                ans[i+1]+=max(0ll,a[i+1]-(a[i+1]+mn[l-1]));
        }
		else{
                ans[i]+=max(0ll,a[i]+mx[l-1]-a[i]);
                ans[i+1]+=max(0ll,a[i+1]-a[i]-mx[l-1]);
        }
   	}
	}
	for(int i=1;i<=n;i++){
		cout << ans[i] << "\n";
	}
	
}

Compilation message (stderr)

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

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