Submission #390688

#	Time	Username	Problem	Language	Result	Execution time	Memory
390688		CaroLinda	Road Construction (JOI21_road_construction)	C++14	100 / 100	2743 ms	630312 KiB

road_construction

#include <bits/stdc++.h>

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

const int MAXN = 250010 ;
const ll inf = 1e15+10LL ;

using namespace std ;

int m(int l, int r) { return (r+l)>>1 ; }
pii Y[MAXN] ;

struct Solve
{
	ll x[MAXN] , y[MAXN] ;
	int seg_index[MAXN] , rt[MAXN] ;

	vector<int> e , d ;
	vector< pair<ll,int> > mn ;

	int create()
	{	
		e.pb(0) ;
		d.pb(0) ;
		mn.pb(mk(inf,0)) ;
		return sz(e)-1 ;		
	}
	int create_and_copy(int pos)
	{
		e.pb(e[pos]) ;
		d.pb(d[pos]) ;
		mn.pb(mn[pos]) ;
		return sz(e)-1 ;
 	}

 	int upd(int pos, int l, int r, int idx, ll val )
 	{
 		int newPos = create_and_copy(pos) ;
 		int aux ;

 		if(l == r) 
 		{
 			mn[newPos] = mk(val,l) ;
 			return newPos ;
 		}

 		if( idx <= m(l,r) )
 		{
 			aux=upd(e[newPos] , l , m(l,r) , idx, val ) ;
 			e[newPos] = aux ;
 		}
 		else
 		{
 			aux = upd(d[newPos] , m(l,r)+1, r, idx, val ) ;
 			d[newPos] = aux ;
 		}

 		mn[newPos] = min(mn[e[newPos]] , mn[d[newPos]]) ;

 		return newPos ;
 	}
 	pair<ll,int> binarySearch(int pos, int l , int r, int R )
 	{
 		if( l > R || !pos ) return mk(inf,0) ;
 		if( r <= R ) return mn[pos] ;

 		pair<ll,int> al = binarySearch(e[pos] , l , m(l,r) , R ) ;
 		pair<ll,int> ar = binarySearch(d[pos] , m(l,r)+1, r, R ) ;

 		return min(al, ar) ;
 	}


} solve[2] ;
 

// ----------------------------------

int N , K ;
pii points[MAXN] ;
priority_queue< pair<ll,int> , vector<pair<ll,int> > , greater< pair<ll,int> > > q[2] ;

int main()
{
	scanf("%d %d", &N, &K ) ;
	lp(i,1,N+1) 
	{
		scanf("%d %d", &points[i].ff, &points[i].ss ) ;
		Y[i] = mk(points[i].ss,i) ;
	}

	sort(Y+1, Y+1+N ) ;

	lp(i,1,N+1) points[i].ss = lower_bound(Y+1, Y+1+N, mk(points[i].ss, i ) ) - Y ;

	sort(points+1, points+1+N ) ;

	lp(i,1,N+1)
	{
		solve[0].x[i] = points[i].ff ;
		solve[0].y[i] = Y[points[i].ss].ff ;
		solve[0].seg_index[i] = points[i].ss ;

		solve[1].x[i] = -points[N-i+1].ff ;
		solve[1].y[i] = Y[points[N-i+1].ss].ff ;
		solve[1].seg_index[i] = points[N-i+1].ss ;
	}

	/*
	lp(i,1,N+1) debug("%lld %lld %d\n" , solve[0].x[i] , solve[0].y[i] , solve[0].seg_index[i] ) ;
	debug("\n") ;

	lp(i,1,N+1) debug("%lld %lld %d\n" , solve[1].x[i] , solve[1].y[i] , solve[1].seg_index[i]) ;
	debug("\n") ;
	*/

	for(int i = 0 ; i < 2 ; i++ )
	{
		solve[i].rt[0] = solve[i].create() ;
		solve[i].rt[1] = solve[i].rt[0] ;

		for(int j = 1 ; j <= N ; j++ ) 
		{
			ll val = solve[i].x[j]+solve[i].y[j] ;
			solve[i].rt[j] = solve[i].upd( solve[i].rt[j] , 1 , N , solve[i].seg_index[j] , -val ) ;

			pair<ll,int> p = solve[i].binarySearch( solve[i].rt[j] , 1 , N , solve[i].seg_index[j]-1 ) ;
			solve[i].rt[j+1] = solve[i].rt[j] ;

			if( p.ss )
			{
				q[i].push( mk(p.ff+val, j) ) ;
				solve[i].rt[j] = solve[i].upd( solve[i].rt[j] , 1 , N , p.ss , inf ) ;
			}
		}	
	}

	for(int trash = 0 ; trash < K ; trash++ )
	{
		int idx = 0 ;
		if( q[0].empty() || ( !q[1].empty() && q[1].top().ff < q[0].top().ff ) ) idx = 1 ;

		printf("%lld\n" , q[idx].top().ff ) ;
		int j = q[idx].top().ss ;
		q[idx].pop() ;

		pair<ll,int> p = solve[idx].binarySearch( solve[idx].rt[j] , 1 , N , solve[idx].seg_index[j]-1 ) ;
		if( !p.ss ) continue ;

		solve[idx].rt[j] = solve[idx].upd( solve[idx].rt[j] , 1 , N , p.ss , inf ) ;
		q[idx].push( mk(p.ff+solve[idx].x[j]+solve[idx].y[j] , j ) ) ;

	}

}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |  scanf("%d %d", &N, &K ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |   scanf("%d %d", &points[i].ff, &points[i].ss ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35