#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 LOG = 20 ;
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 ;
int dp[2][LOG][MAX] , dist[2][LOG][MAX] ;
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 ;
}
}
bool isOn(int m, int i) { return ((1<<i)&m) != 0 ; }
int getDist( bool clockwise , int a, int b )
{
if(!clockwise)
{
if(b < a) return a - b ;
return a + n - b ;
}
if( b > a ) return b-a ;
return n-a+b ;
}
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]; } ) ;
memset(dp, -1, sizeof dp ) ;
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) ) ;
dp[0][0][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) ) ;
dp[1][0][e] = p.ss ;
seg.upd(1,0,n-1,e,e, -h[e] ) ;
}
lp(i,0,2)
lp(j,0,n)
if(dp[i][0][j] != -1)
dist[i][0][j] = getDist(i, j , dp[i][0][j] ) ;
lp(i,0,2)
lp(j,1,LOG)
lp(g,0,n)
{
if(dp[i][j-1][g] == -1) continue ;
dp[i][j][g] = dp[i][j-1][ dp[i][j-1][g] ] ;
dist[i][j][g] = dist[i][j-1][g] + dist[i][j-1][ dp[i][j-1][g] ] ;
}
/*for(auto e : h ) cout << e << " " ;
cout << endl ; */
}
int compare_plants(int x, int y)
{
if( 2*k > n || getDist(false, x, y) < k || getDist(true, x, y) < k)
return h[x] > h[y] ? 1 : -1 ;
for(int cur : {x,y} )
for(int type = 0 ; type < 2 ; type++ )
{
int filho = cur , _filho ;
int other = (cur == x ) ? y : x ;
int d = getDist(type, cur, other) ;
for(int i = LOG-1 ; i >= 0 ; i-- )
{
_filho = dp[type][i][filho] ;
if(_filho == -1 || dist[type][i][filho] > d ) continue ;
//cout << cur << " " << type << " " << filho << " " << h[filho] << " " << _filho << " " << (1<<i) << endl ;
int distToCur = getDist(type, _filho, cur ) ;
int distToOther = getDist(type, _filho, other ) ;
if(distToOther > distToCur ) continue ;
if(distToOther < k )
{
if(h[other] <= h[_filho] )
return (cur == x) ? 1 : -1 ;
}
else if(h[_filho] > h[other] )filho = _filho , d -= dist[type][i][filho] ;
}
if(h[other] <= h[filho] && getDist(type, filho, other) < k )
return (cur == x) ? 1 : -1 ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
6 ms |
9728 KB |
Output is correct |
3 |
Correct |
30 ms |
53632 KB |
Output is correct |
4 |
Correct |
30 ms |
53632 KB |
Output is correct |
5 |
Correct |
30 ms |
53624 KB |
Output is correct |
6 |
Correct |
110 ms |
56440 KB |
Output is correct |
7 |
Correct |
233 ms |
59896 KB |
Output is correct |
8 |
Correct |
763 ms |
84524 KB |
Output is correct |
9 |
Correct |
830 ms |
88312 KB |
Output is correct |
10 |
Correct |
904 ms |
87928 KB |
Output is correct |
11 |
Correct |
959 ms |
85624 KB |
Output is correct |
12 |
Correct |
977 ms |
86652 KB |
Output is correct |
13 |
Correct |
918 ms |
87672 KB |
Output is correct |
14 |
Correct |
1043 ms |
87672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
6 ms |
9728 KB |
Output is correct |
3 |
Correct |
6 ms |
9728 KB |
Output is correct |
4 |
Correct |
6 ms |
9728 KB |
Output is correct |
5 |
Correct |
7 ms |
9728 KB |
Output is correct |
6 |
Correct |
10 ms |
9984 KB |
Output is correct |
7 |
Correct |
88 ms |
13304 KB |
Output is correct |
8 |
Correct |
8 ms |
9856 KB |
Output is correct |
9 |
Correct |
10 ms |
9984 KB |
Output is correct |
10 |
Correct |
92 ms |
13304 KB |
Output is correct |
11 |
Correct |
84 ms |
13176 KB |
Output is correct |
12 |
Correct |
90 ms |
13432 KB |
Output is correct |
13 |
Correct |
94 ms |
13304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
6 ms |
9728 KB |
Output is correct |
3 |
Correct |
6 ms |
9728 KB |
Output is correct |
4 |
Correct |
6 ms |
9728 KB |
Output is correct |
5 |
Correct |
7 ms |
9728 KB |
Output is correct |
6 |
Correct |
10 ms |
9984 KB |
Output is correct |
7 |
Correct |
88 ms |
13304 KB |
Output is correct |
8 |
Correct |
8 ms |
9856 KB |
Output is correct |
9 |
Correct |
10 ms |
9984 KB |
Output is correct |
10 |
Correct |
92 ms |
13304 KB |
Output is correct |
11 |
Correct |
84 ms |
13176 KB |
Output is correct |
12 |
Correct |
90 ms |
13432 KB |
Output is correct |
13 |
Correct |
94 ms |
13304 KB |
Output is correct |
14 |
Correct |
133 ms |
15440 KB |
Output is correct |
15 |
Correct |
816 ms |
37240 KB |
Output is correct |
16 |
Correct |
129 ms |
15352 KB |
Output is correct |
17 |
Correct |
791 ms |
37240 KB |
Output is correct |
18 |
Correct |
448 ms |
37212 KB |
Output is correct |
19 |
Correct |
455 ms |
37240 KB |
Output is correct |
20 |
Correct |
720 ms |
37240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
53632 KB |
Output is correct |
2 |
Correct |
30 ms |
53632 KB |
Output is correct |
3 |
Incorrect |
156 ms |
56824 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
6 ms |
9728 KB |
Output is correct |
3 |
Correct |
31 ms |
53760 KB |
Output is correct |
4 |
Correct |
30 ms |
53624 KB |
Output is correct |
5 |
Correct |
30 ms |
53624 KB |
Output is correct |
6 |
Incorrect |
32 ms |
53632 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
6 ms |
9728 KB |
Output is correct |
3 |
Correct |
31 ms |
53632 KB |
Output is correct |
4 |
Correct |
30 ms |
53632 KB |
Output is correct |
5 |
Incorrect |
33 ms |
53752 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9728 KB |
Output is correct |
2 |
Correct |
6 ms |
9728 KB |
Output is correct |
3 |
Correct |
30 ms |
53632 KB |
Output is correct |
4 |
Correct |
30 ms |
53632 KB |
Output is correct |
5 |
Correct |
30 ms |
53624 KB |
Output is correct |
6 |
Correct |
110 ms |
56440 KB |
Output is correct |
7 |
Correct |
233 ms |
59896 KB |
Output is correct |
8 |
Correct |
763 ms |
84524 KB |
Output is correct |
9 |
Correct |
830 ms |
88312 KB |
Output is correct |
10 |
Correct |
904 ms |
87928 KB |
Output is correct |
11 |
Correct |
959 ms |
85624 KB |
Output is correct |
12 |
Correct |
977 ms |
86652 KB |
Output is correct |
13 |
Correct |
918 ms |
87672 KB |
Output is correct |
14 |
Correct |
1043 ms |
87672 KB |
Output is correct |
15 |
Correct |
6 ms |
9728 KB |
Output is correct |
16 |
Correct |
6 ms |
9728 KB |
Output is correct |
17 |
Correct |
6 ms |
9728 KB |
Output is correct |
18 |
Correct |
6 ms |
9728 KB |
Output is correct |
19 |
Correct |
7 ms |
9728 KB |
Output is correct |
20 |
Correct |
10 ms |
9984 KB |
Output is correct |
21 |
Correct |
88 ms |
13304 KB |
Output is correct |
22 |
Correct |
8 ms |
9856 KB |
Output is correct |
23 |
Correct |
10 ms |
9984 KB |
Output is correct |
24 |
Correct |
92 ms |
13304 KB |
Output is correct |
25 |
Correct |
84 ms |
13176 KB |
Output is correct |
26 |
Correct |
90 ms |
13432 KB |
Output is correct |
27 |
Correct |
94 ms |
13304 KB |
Output is correct |
28 |
Correct |
133 ms |
15440 KB |
Output is correct |
29 |
Correct |
816 ms |
37240 KB |
Output is correct |
30 |
Correct |
129 ms |
15352 KB |
Output is correct |
31 |
Correct |
791 ms |
37240 KB |
Output is correct |
32 |
Correct |
448 ms |
37212 KB |
Output is correct |
33 |
Correct |
455 ms |
37240 KB |
Output is correct |
34 |
Correct |
720 ms |
37240 KB |
Output is correct |
35 |
Correct |
31 ms |
53632 KB |
Output is correct |
36 |
Correct |
30 ms |
53632 KB |
Output is correct |
37 |
Incorrect |
156 ms |
56824 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |