oj.uz

Submission #308591

# Submission time Handle Problem Language Result Execution time Memory
308591 2020-10-01T14:53:04 Z CaroLinda Comparing Plants (IOI20_plants) C++14
0 / 100
 14 ms 17664 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] ;

	Seg()
	{
		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 ;
vector<pii> interval[MAX] ;

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

		//debug("Em %d, tenho %d %d\n" , x , p.ff, p.ss ) ;

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

		//debug("Processing %d\n",  x ) ;

		h[x] = last-- ;
		
		seg.upd(1,0,n-1, x , x , inf ) ;
		for(auto e : interval[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 ;

	interval[0].push_back( mk(n-k+1,n-1) ) ;
	lp(i,1,n)
	{
		interval[i].push_back( mk(max(0,i-k+1) , i-1) ) ;

		if( i >= k-1 ) continue ;
		
		int falta = k-1 - i ;
		interval[i].pb( mk( n-falta , n-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) ;

		//debug("Iniciando com %d %d\n", p.ff , p.ss ) ;

		if(p.ff != 0) break ;

		extract(p.ss) ;

	}

	lp(i,0,n)
		assert(h[i] != 0 ) ;

}

int compare_plants(int x, int y) 
{
	return h[x] > h[y] ;	
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 13 ms 17568 KB Output is correct
3 Incorrect 13 ms 17536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17536 KB Output is correct
2 Correct 12 ms 17512 KB Output is correct
3 Incorrect 11 ms 17556 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17536 KB Output is correct
2 Correct 12 ms 17512 KB Output is correct
3 Incorrect 11 ms 17556 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 17536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Incorrect 13 ms 17536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17664 KB Output is correct
2 Correct 13 ms 17592 KB Output is correct
3 Incorrect 13 ms 17536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 13 ms 17568 KB Output is correct
3 Incorrect 13 ms 17536 KB Output isn't correct
4 Halted 0 ms 0 KB -