oj.uz

Submission #308658

# Submission time Handle Problem Language Result Execution time Memory
308658 2020-10-01T16:31:14 Z CaroLinda Comparing Plants (IOI20_plants) C++14
38 / 100
 4000 ms 48212 KB 
#include "plants.h"
#include <bits/stdc++.h>

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

const int MAX = 2e5+10 ;
const int inf = 1e8+10 ;

using namespace std ;

struct Seg
{

	ll lz[MAX*4] , mn[MAX*4];
	int idx[MAX*4] ;

	void clean()
	{
		memset(lz, 0, sizeof lz) ;
		memset(mn, 0, sizeof mn) ;
	}

	int m(int l, int r) { return (l+r)>>1 ; }
	void refresh(int pos, int l, int r)
	{
		if(!lz[pos]) return ;

		mn[pos] += lz[pos] ;

		if(l == r) return (void)(lz[pos] = 0 ) ;

		lz[pos<<1] += lz[pos] ;
		lz[pos<<1|1] += lz[pos] ;

		lz[pos] = 0 ;

	}

	void upd(int pos, int l, int r, int beg, int en , int val )
	{
		refresh(pos,l,r) ;

		if(l > en || r < beg ) return ;
		if(l >= beg && r <= en)
		{
			lz[pos] += (ll)val ;
			refresh(pos,l,r) ;
			if(l == r) idx[pos] = l ;
			return ;
		}

		upd(pos<<1 , l, m(l,r) , beg, en, val ) ;
		upd(pos<<1|1 , m(l,r)+1,r, beg, en, val ) ;

		if(mn[pos<<1] <= mn[pos<<1|1])
		{
			idx[pos] = idx[pos<<1] ;
			mn[pos] = mn[pos<<1] ;
		}
		else 
		{
			idx[pos] = idx[pos<<1|1] ;
			mn[pos] = mn[pos<<1|1] ;
		}

	}

	pii qry(int pos, int l, int r, int beg, int en )
	{
		refresh(pos,l,r) ;
		if( l > en || r < beg ) return mk(inf, -1) ;
		if(l >= beg && r <= en) return mk( mn[pos] , idx[pos] ) ;

		pii al = qry(pos<<1 , l, m(l,r) , beg, en ) ;
		pii ar = qry(pos<<1|1 , m(l,r)+1,r, beg, en ) ;

		if( al.ff <= ar.ff ) return al ;
		return ar ;
	}

} seg ;

int n , last , k ;
vector<int> h , lef , rig ;
vector<pii> intervalLeft[MAX] , intervalRight[MAX] ;

void extract(int x)
{
	while(true)
	{
	
		pii p = mk(inf, -1) ;
		
		for(auto e : intervalLeft[x] ) 
			p = min(p, seg.qry(1,0,n-1, e.ff, e.ss) ) ;

		if(p.ff == 0) 
		{
			extract(p.ss) ;
			continue ;
		}

		h[x] = last-- ;
		
		seg.upd(1,0,n-1, x , x , inf ) ;
		for(auto e : intervalLeft[x] ) seg.upd(1,0,n-1, e.ff, e.ss, -1) ;

		return ;

	}

}

void init(int K, vector<int> r) 
{
	k = K ;
	n = sz(r) ;
	h.resize(n,0) ;
	last = n ;

	//Find intervals
	intervalLeft[0].push_back( mk(n-k+1,n-1) ) ;
	lp(i,1,n)
	{
		intervalLeft[i].push_back( mk(max(0,i-k+1) , i-1) ) ;

		if( i >= k-1 ) continue ;
		
		int falta = k-1 - i ;
		intervalLeft[i].pb( mk( n-falta , n-1 ) ) ;

	}
	intervalRight[n-1].pb( mk( 0 , k-2 ) ) ;
	lp(i,0,n-1)
	{
		intervalRight[i].pb( mk( i+1, min(n-1, i+k-1) ) ) ;

		if( i+k-1 <= n-1 ) continue ;

		int lef = k-1 - (n-i-1) ;
		intervalRight[i].pb(  mk(0,lef-1)) ;

	}

	for(int i = 0 ; i < n ; i++ ) 
		seg.upd(1,0,n-1, i , i , r[i] ); 

	while(true)
	{
		pii p = seg.qry(1,0,n-1,0,n-1) ;

		if(p.ff != 0) break ;

		extract(p.ss) ;

	}

	if(2*k > n ) return ;

	seg.clean() ;

	vector<int> idx(n) ;
	iota(all(idx) , 0 ) ;
	sort(all(idx), [&](int i, int j){ return h[i] < h[j]; }  ) ;

	lef.resize(n,0) ;
	rig.resize(n,0) ;

	for(auto e : idx )
	{
		pii p = mk(0 , -1 ) ;
		for(auto e : intervalLeft[e] )
			p = min(p , seg.qry(1,0,n-1, e.ff, e.ss) ) ;

		lef[e] = p.ss ;

		p = mk(0, -1 ) ;
		for(auto e : intervalRight[e] ) 
			p = min(p, seg.qry(1,0,n-1, e.ff, e.ss) ) ;

		rig[e] = p.ss ;

		//debug("Just processed %d, with %d %d\n" , e , lef[e] , rig[e] ) ;

		seg.upd(1,0,n-1,e,e, -h[e] ) ;

	}

}

int compare_plants(int x, int y) 
{
	if( 2*k > n )
		return h[x] > h[y] ? 1 : -1 ;

	
	for(int e : {x,y} ) 
	{
		vector<int> fila ;
		fila.pb(e) ;
		int ini = 0 ;

		vector<bool> vis(n, false) ;
		vis[e] = true ;

		while( ini < sz(fila) )
		{
			int curr = fila[ini++] ;

			if(e == x && curr == y) return 1 ;
			if( e == y && curr == x ) return -1 ;

			for(int i : {lef[curr] , rig[curr]})
				if(i != -1 && !vis[i])
				{
					vis[i] = true ;
					fila.pb(i) ;
				}

		}
	}

	return 0 ;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 15 ms 22272 KB Output is correct
4 Correct 14 ms 22272 KB Output is correct
5 Correct 15 ms 22272 KB Output is correct
6 Correct 144 ms 25184 KB Output is correct
7 Correct 829 ms 27128 KB Output is correct
8 Correct 990 ms 43896 KB Output is correct
9 Correct 1399 ms 43896 KB Output is correct
10 Execution timed out 4102 ms 43896 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 9728 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 89 ms 13300 KB Output is correct
8 Correct 9 ms 9856 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 91 ms 13304 KB Output is correct
11 Correct 83 ms 13176 KB Output is correct
12 Correct 84 ms 13432 KB Output is correct
13 Correct 88 ms 13304 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 9728 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 89 ms 13300 KB Output is correct
8 Correct 9 ms 9856 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 91 ms 13304 KB Output is correct
11 Correct 83 ms 13176 KB Output is correct
12 Correct 84 ms 13432 KB Output is correct
13 Correct 88 ms 13304 KB Output is correct
14 Correct 132 ms 15352 KB Output is correct
15 Correct 814 ms 37368 KB Output is correct
16 Correct 132 ms 15420 KB Output is correct
17 Correct 816 ms 37240 KB Output is correct
18 Correct 452 ms 37240 KB Output is correct
19 Correct 463 ms 37496 KB Output is correct
20 Correct 739 ms 37276 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 22272 KB Output is correct
2 Correct 15 ms 22272 KB Output is correct
3 Correct 2136 ms 25268 KB Output is correct
4 Execution timed out 4083 ms 48212 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 15 ms 22272 KB Output is correct
4 Correct 14 ms 22272 KB Output is correct
5 Correct 15 ms 22400 KB Output is correct
6 Correct 20 ms 22528 KB Output is correct
7 Correct 106 ms 22904 KB Output is correct
8 Correct 183 ms 22904 KB Output is correct
9 Correct 144 ms 22904 KB Output is correct
10 Correct 179 ms 22904 KB Output is correct
11 Correct 130 ms 22904 KB Output is correct
12 Correct 178 ms 22904 KB Output is correct
13 Correct 23 ms 10368 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 14 ms 22272 KB Output is correct
4 Correct 15 ms 22272 KB Output is correct
5 Correct 27 ms 22400 KB Output is correct
6 Execution timed out 4097 ms 44024 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 15 ms 22272 KB Output is correct
4 Correct 14 ms 22272 KB Output is correct
5 Correct 15 ms 22272 KB Output is correct
6 Correct 144 ms 25184 KB Output is correct
7 Correct 829 ms 27128 KB Output is correct
8 Correct 990 ms 43896 KB Output is correct
9 Correct 1399 ms 43896 KB Output is correct
10 Execution timed out 4102 ms 43896 KB Time limit exceeded
11 Halted 0 ms 0 KB -