oj.uz

Submission #308619

# Submission time Handle Problem Language Result Execution time Memory
308619 2020-10-01T15:09:25 Z CaroLinda Comparing Plants (IOI20_plants) C++14
44 / 100
 786 ms 34296 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] ? 1 : -1 ;
}

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17568 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 11 ms 17536 KB Output is correct
6 Correct 14 ms 17664 KB Output is correct
7 Correct 91 ms 20728 KB Output is correct
8 Correct 12 ms 17664 KB Output is correct
9 Correct 15 ms 17664 KB Output is correct
10 Correct 98 ms 20856 KB Output is correct
11 Correct 88 ms 20604 KB Output is correct
12 Correct 85 ms 20728 KB Output is correct
13 Correct 90 ms 20856 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17568 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 11 ms 17536 KB Output is correct
6 Correct 14 ms 17664 KB Output is correct
7 Correct 91 ms 20728 KB Output is correct
8 Correct 12 ms 17664 KB Output is correct
9 Correct 15 ms 17664 KB Output is correct
10 Correct 98 ms 20856 KB Output is correct
11 Correct 88 ms 20604 KB Output is correct
12 Correct 85 ms 20728 KB Output is correct
13 Correct 90 ms 20856 KB Output is correct
14 Correct 131 ms 21496 KB Output is correct
15 Correct 778 ms 30712 KB Output is correct
16 Correct 131 ms 21624 KB Output is correct
17 Correct 772 ms 30712 KB Output is correct
18 Correct 427 ms 30712 KB Output is correct
19 Correct 433 ms 30840 KB Output is correct
20 Correct 730 ms 30712 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17536 KB Output is correct
2 Correct 10 ms 17536 KB Output is correct
3 Correct 86 ms 20476 KB Output is correct
4 Correct 386 ms 34296 KB Output is correct
5 Correct 457 ms 30968 KB Output is correct
6 Correct 684 ms 30584 KB Output is correct
7 Correct 785 ms 30584 KB Output is correct
8 Correct 786 ms 30584 KB Output is correct
9 Correct 417 ms 30856 KB Output is correct
10 Correct 423 ms 30584 KB Output is correct
11 Correct 361 ms 30584 KB Output is correct
12 Correct 372 ms 30712 KB Output is correct
13 Correct 430 ms 30584 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 12 ms 17536 KB Output is correct
3 Incorrect 12 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 11 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Incorrect 12 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 18 ms 17536 KB Output is correct
2 Correct 13 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Incorrect 11 ms 17536 KB Output isn't correct
5 Halted 0 ms 0 KB -