#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] += 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) ;
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) ;
}
}
int compare_plants(int x, int y)
{
return h[x] > h[y] ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
17536 KB |
Output is correct |
2 |
Correct |
10 ms |
17536 KB |
Output is correct |
3 |
Incorrect |
10 ms |
17536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
17536 KB |
Output is correct |
2 |
Correct |
10 ms |
17536 KB |
Output is correct |
3 |
Incorrect |
10 ms |
17536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
17536 KB |
Output is correct |
2 |
Correct |
10 ms |
17536 KB |
Output is correct |
3 |
Incorrect |
10 ms |
17536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
17536 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
17536 KB |
Output is correct |
2 |
Correct |
10 ms |
17536 KB |
Output is correct |
3 |
Incorrect |
12 ms |
17536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
17536 KB |
Output is correct |
2 |
Correct |
10 ms |
17536 KB |
Output is correct |
3 |
Incorrect |
10 ms |
17536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
17536 KB |
Output is correct |
2 |
Correct |
10 ms |
17536 KB |
Output is correct |
3 |
Incorrect |
10 ms |
17536 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |