oj.uz

Submission #390688

# Submission time Handle Problem Language Result Execution time Memory
390688 2021-04-16T14:04:47 Z CaroLinda Road Construction (JOI21_road_construction) C++14
100 / 100
 2743 ms 630312 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 83428 KB Output is correct
2 Correct 520 ms 88508 KB Output is correct
3 Correct 387 ms 89152 KB Output is correct
4 Correct 375 ms 86444 KB Output is correct
5 Correct 404 ms 87976 KB Output is correct
6 Correct 5 ms 2884 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2743 ms 628888 KB Output is correct
2 Correct 2554 ms 629668 KB Output is correct
3 Correct 394 ms 88644 KB Output is correct
4 Correct 2337 ms 629256 KB Output is correct
5 Correct 2180 ms 629408 KB Output is correct
6 Correct 2175 ms 629420 KB Output is correct
7 Correct 2341 ms 628752 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 622620 KB Output is correct
2 Correct 1752 ms 622664 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1677 ms 622704 KB Output is correct
5 Correct 1709 ms 622668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 622620 KB Output is correct
2 Correct 1752 ms 622664 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1677 ms 622704 KB Output is correct
5 Correct 1709 ms 622668 KB Output is correct
6 Correct 1835 ms 622788 KB Output is correct
7 Correct 1798 ms 622708 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1767 ms 622656 KB Output is correct
11 Correct 1701 ms 622720 KB Output is correct
12 Correct 1760 ms 622644 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 83428 KB Output is correct
2 Correct 520 ms 88508 KB Output is correct
3 Correct 387 ms 89152 KB Output is correct
4 Correct 375 ms 86444 KB Output is correct
5 Correct 404 ms 87976 KB Output is correct
6 Correct 5 ms 2884 KB Output is correct
7 Correct 1523 ms 313616 KB Output is correct
8 Correct 1502 ms 313520 KB Output is correct
9 Correct 440 ms 86188 KB Output is correct
10 Correct 1155 ms 313044 KB Output is correct
11 Correct 1367 ms 316504 KB Output is correct
12 Correct 927 ms 313236 KB Output is correct
13 Correct 1120 ms 352668 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 83428 KB Output is correct
2 Correct 520 ms 88508 KB Output is correct
3 Correct 387 ms 89152 KB Output is correct
4 Correct 375 ms 86444 KB Output is correct
5 Correct 404 ms 87976 KB Output is correct
6 Correct 5 ms 2884 KB Output is correct
7 Correct 2743 ms 628888 KB Output is correct
8 Correct 2554 ms 629668 KB Output is correct
9 Correct 394 ms 88644 KB Output is correct
10 Correct 2337 ms 629256 KB Output is correct
11 Correct 2180 ms 629408 KB Output is correct
12 Correct 2175 ms 629420 KB Output is correct
13 Correct 2341 ms 628752 KB Output is correct
14 Correct 1865 ms 622620 KB Output is correct
15 Correct 1752 ms 622664 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1677 ms 622704 KB Output is correct
18 Correct 1709 ms 622668 KB Output is correct
19 Correct 1835 ms 622788 KB Output is correct
20 Correct 1798 ms 622708 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1767 ms 622656 KB Output is correct
24 Correct 1701 ms 622720 KB Output is correct
25 Correct 1760 ms 622644 KB Output is correct
26 Correct 1523 ms 313616 KB Output is correct
27 Correct 1502 ms 313520 KB Output is correct
28 Correct 440 ms 86188 KB Output is correct
29 Correct 1155 ms 313044 KB Output is correct
30 Correct 1367 ms 316504 KB Output is correct
31 Correct 927 ms 313236 KB Output is correct
32 Correct 1120 ms 352668 KB Output is correct
33 Correct 2720 ms 630312 KB Output is correct
34 Correct 2718 ms 630192 KB Output is correct
35 Correct 2344 ms 629568 KB Output is correct
36 Correct 2012 ms 629404 KB Output is correct
37 Correct 2058 ms 629692 KB Output is correct
38 Correct 2252 ms 628572 KB Output is correct