Submission #386116

#	Time	Username	Problem	Language	Result	Execution time	Memory
386116		CaroLinda	Snowball (JOI21_ho_t2)	C++14	100 / 100	1104 ms	18884 KiB

Main

#include <bits/stdc++.h>
 
#define lp(i,a,b) for(int i = a ; i < b;  i++)
#define ll long long
#define all(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define ff first
#define ss second	

const int MAXN = 2e5+10 ;

using namespace std ;

int N , Q ;
ll L[MAXN] , R[MAXN] ;
ll X[MAXN] ;
vector< pair<ll,int> > pref , suf ;

int main()
{
	scanf("%d %d", &N , &Q ) ;
	for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &X[i] ) ;

	ll t = 0 ;
	pref.pb(mk(0,0)) ;
	suf.pb(mk(0,0)) ;

	for(int i = 1 ; i <= Q ; i++ )
	{
		ll k ;
		scanf("%lld", &k ) ;
		t += k ;
		pref.pb(mk(t,i)) ;
		suf.pb(mk(t,i)) ;
	}

	sort(all(pref)) ;
	sort(all(suf)) ;

	for(int i = sz(suf)-2 ; i >= 0 ; i-- )
		suf[i].ss = min(suf[i].ss , suf[i+1].ss) ;

	for(int i = 1 ; i < sz(pref); i++ )
		pref[i].ss = min(pref[i-1].ss, pref[i].ss ) ;

	R[N] = suf.back().ff+X[N] ;

	for(int i = 1 ; i < N ; i++ )
	{
		ll l = X[i] , r = min(X[i+1],X[i]+suf.back().ff) , mid , best = X[i] ;

		while(l <= r)
		{
			if( l == r-1 ) mid = l ;
			else mid = (l+r)>>1 ;

			int t_mine = lower_bound(all(suf), mk(mid-X[i], -1) )->second ;
			
			auto it = upper_bound(all(pref), mk(mid-X[i+1],-1) ) ;
			int t_yours = Q+10 ;

			if(it != pref.begin() )
			{
				it-- ;
				t_yours = it->second ;
			}

			if(t_mine < t_yours) { best= mid ; l = mid+1 ; }
			else r = mid-1 ;

		}

		R[i] = best ;
	}

	L[1] = min(X[1]+pref[0].ff, X[1] ) ;

	for(int i = 2 ; i<= N ; i++ )
	{
		L[i] = min(X[i] , X[i]+pref[0].ff ) ;

		if( R[i-1] >= L[i] )
			L[i] = R[i-1] ;
	}

	lp(i,1,N+1) printf("%lld\n" , R[i]-L[i] ) ;
	//lp(i,1,N+1) printf("%lld %lld\n" , L[i] ,R[i]) ;

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%d %d", &N , &Q ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:25:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &X[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%lld", &k ) ;
      |   ~~~~~^~~~~~~~~~~~~

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