#include "plants.h"
#include <queue>
#include <bitset>
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
const int MN = 2e5+10;
const int INF = 0x3f3f3f3f;
int N, K, ts[MN], ctr, ord[MN];
bool v[MN], done[MN];
//Minmax Segtree
struct minmax
{
public:
int min, max;
minmax(int _mn=INF, int _mx=-INF): min(_mn), max(_mx) {}
minmax& operator += (const int& o) {min += o, max += o; return *this;}
minmax& operator -= (const int& o) {min -= o, max -= o; return *this;}
minmax& operator += (const minmax& o) {ckmin(min, o.min); ckmax(max, o.max); return *this;}
friend minmax operator + (minmax a, const int& b) {return a+=b;}
friend minmax operator - (minmax a, const int& b) {return a-=b;}
friend minmax operator + (minmax a, const minmax& b) {return a+=b;}
bool contains(int x) {return min <= x && x <= max;}
bool contains(const minmax& x) {return min <= x.min && x.max <= max;}
} range[MN];
minmax mv[1 << 19];
minmax mqry(int n, int l, int r, int ql, int qr)
{
if(ql <= l && r <= qr) return mv[n];
else
{
int m=l+(r-l)/2; minmax f;
if(ql < m) f += mqry(n<<1, l, m, ql, qr);
if(m < qr) f += mqry(n<<1|1, m, r, ql, qr);
return f;
}
}
void mupd(int n, int l, int r, int q, minmax val)
{
if(r-l>1)
{
int m=l+(r-l)/2;
if(q < m) mupd(n<<1, l, m, q, val);
else mupd(n<<1|1, m, r, q, val);
mv[n]=mv[n<<1]+mv[n<<1|1];
}
else
mv[n]=val;
}
//R segment tree
int rv[1 << 19], rz[1 << 19];
void rupd(int n, int x) {rv[n] += x, rz[n] += x;}
void rdown(int n)
{
if(rz[n])
{
rupd(n<<1, rz[n]);
rupd(n<<1|1, rz[n]);
rz[n]=0;
}
}
void rupd(int n, int l, int r, int ql, int qr, int x)
{
if(ql <= l&&r <= qr) rupd(n, x);
else
{
int m=l+(r-l)/2;
rdown(n);
if(ql < m) rupd(n<<1, l, m, ql, qr, x);
if(m < qr) rupd(n<<1|1, m, r, ql, qr, x);
rv[n] = std::min(rv[n<<1], rv[n<<1|1]);
}
}
int rqry(int n, int l, int r, int ql) // return leftmost zero
{
if(rv[n] > 0) return r;
else if(r-l>1)
{
int m=l+(r-l)/2, f=m;
rdown(n);
if(ql < m) f=rqry(n<<1, l, m, ql);
if(f == m) f=rqry(n<<1|1, m, r, ql);
return f;
}
else return l;
}
void init(int k, std::vector<int> r) {
K=k, N=r.size();
std::queue<int> q;
int zc=0;
for(int i=N-K;i<N;++i)
zc += !r[i];
for(int i=0;i<N;++i)
{
zc -= !r[(N-K+i)%N];
if(zc==0 && r[i]==0)
q.push(i);
zc += !r[i];
}
for(int i=0;i<N;++i)
rupd(1, 0, N, i, i+1, r[i]);
for(;!q.empty();)
{
int n=q.front(); q.pop();
if(done[n]) continue;
// check
int loc = rqry(1, 0, N, n-K+1);
//printf("?? %d (%d)\n", n, loc);
if(loc < n) continue;
if(n-K+1 < 0 && rqry(1, 0, N, n-K+1+N) < N) continue;
// add
rupd(1, 0, N, n, n+1, INF);
//printf("TEST [%d] %d\n", n, rqry(1, 0, N, 0));
rupd(1, 0, N, n-K+1, n, -1);
if(n-K+1 < 0) rupd(1, 0, N, n-K+1+N, N, -1);
loc = rqry(1, 0, N, n);
if(loc < std::min(N, n+K))
q.push(loc);
else if(n+K>N)
{
loc = rqry(1, 0, N, 0);
if(loc<n+K-N)
q.push(loc);
}
loc = N;
if(n-K+1 < 0)
loc = rqry(1, 0, N, n-K+1+N);
if(loc < N)
q.push(loc);
else
{
loc = rqry(1, 0, N, n-K+1);
if(loc < n)
q.push(loc);
}
//modify ans
ts[ctr]=n;
ord[n]=ctr++;
done[n]=1;
}
for(int i=N-1, n;i>=0;--i)
{
n=ts[i];
range[n] = minmax(n, n);
range[n] += mqry(1, 0, N, n-K+1, n+K);
if(n+K>N) range[n] += mqry(1, 0, N, 0, n+K-N)+N;
if(n-K+1<0) range[n] += mqry(1, 0, N, n-K+1+N, N)-N;
mupd(1, 0, N, n, range[n]);
//printf("%d: %d <-> %d\n", n, range[n].min, range[n].max);
}
return;
}
bool cover(int a, int b) // is a > b?
{
if(ord[a]>ord[b]) return 0;
return range[a].contains(range[b]) || range[a].contains(range[b]+N) || range[a].contains(range[b]-N);
}
int compare_plants(int x, int y)
{
if(cover(x, y)) return 1;
if(cover(y, x)) return -1;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5964 KB |
Output is correct |
2 |
Correct |
3 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
5964 KB |
Output is correct |
4 |
Correct |
4 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5976 KB |
Output is correct |
6 |
Correct |
72 ms |
8692 KB |
Output is correct |
7 |
Correct |
127 ms |
9552 KB |
Output is correct |
8 |
Correct |
420 ms |
15316 KB |
Output is correct |
9 |
Correct |
455 ms |
15164 KB |
Output is correct |
10 |
Correct |
421 ms |
15228 KB |
Output is correct |
11 |
Correct |
396 ms |
15208 KB |
Output is correct |
12 |
Correct |
365 ms |
15112 KB |
Output is correct |
13 |
Correct |
357 ms |
15236 KB |
Output is correct |
14 |
Correct |
396 ms |
15192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5964 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
3 ms |
5964 KB |
Output is correct |
4 |
Correct |
5 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5964 KB |
Output is correct |
6 |
Correct |
7 ms |
5964 KB |
Output is correct |
7 |
Correct |
92 ms |
9276 KB |
Output is correct |
8 |
Correct |
5 ms |
5964 KB |
Output is correct |
9 |
Correct |
7 ms |
5964 KB |
Output is correct |
10 |
Correct |
81 ms |
9252 KB |
Output is correct |
11 |
Correct |
73 ms |
9124 KB |
Output is correct |
12 |
Correct |
73 ms |
9368 KB |
Output is correct |
13 |
Correct |
81 ms |
9364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5964 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
3 ms |
5964 KB |
Output is correct |
4 |
Correct |
5 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5964 KB |
Output is correct |
6 |
Correct |
7 ms |
5964 KB |
Output is correct |
7 |
Correct |
92 ms |
9276 KB |
Output is correct |
8 |
Correct |
5 ms |
5964 KB |
Output is correct |
9 |
Correct |
7 ms |
5964 KB |
Output is correct |
10 |
Correct |
81 ms |
9252 KB |
Output is correct |
11 |
Correct |
73 ms |
9124 KB |
Output is correct |
12 |
Correct |
73 ms |
9368 KB |
Output is correct |
13 |
Correct |
81 ms |
9364 KB |
Output is correct |
14 |
Correct |
116 ms |
10192 KB |
Output is correct |
15 |
Correct |
733 ms |
16040 KB |
Output is correct |
16 |
Correct |
118 ms |
9560 KB |
Output is correct |
17 |
Correct |
737 ms |
16196 KB |
Output is correct |
18 |
Correct |
502 ms |
15996 KB |
Output is correct |
19 |
Correct |
492 ms |
15992 KB |
Output is correct |
20 |
Correct |
800 ms |
16000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5964 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
72 ms |
8840 KB |
Output is correct |
4 |
Correct |
400 ms |
15828 KB |
Output is correct |
5 |
Correct |
499 ms |
15988 KB |
Output is correct |
6 |
Correct |
645 ms |
16012 KB |
Output is correct |
7 |
Correct |
731 ms |
15904 KB |
Output is correct |
8 |
Correct |
693 ms |
15920 KB |
Output is correct |
9 |
Correct |
441 ms |
15904 KB |
Output is correct |
10 |
Correct |
448 ms |
15876 KB |
Output is correct |
11 |
Correct |
418 ms |
15220 KB |
Output is correct |
12 |
Correct |
437 ms |
15876 KB |
Output is correct |
13 |
Correct |
516 ms |
16000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5964 KB |
Output is correct |
2 |
Correct |
3 ms |
5964 KB |
Output is correct |
3 |
Correct |
3 ms |
5964 KB |
Output is correct |
4 |
Correct |
4 ms |
5964 KB |
Output is correct |
5 |
Incorrect |
4 ms |
5964 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5964 KB |
Output is correct |
2 |
Correct |
4 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
5964 KB |
Output is correct |
4 |
Correct |
3 ms |
5964 KB |
Output is correct |
5 |
Incorrect |
5 ms |
5964 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5964 KB |
Output is correct |
2 |
Correct |
3 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
5964 KB |
Output is correct |
4 |
Correct |
4 ms |
5964 KB |
Output is correct |
5 |
Correct |
4 ms |
5976 KB |
Output is correct |
6 |
Correct |
72 ms |
8692 KB |
Output is correct |
7 |
Correct |
127 ms |
9552 KB |
Output is correct |
8 |
Correct |
420 ms |
15316 KB |
Output is correct |
9 |
Correct |
455 ms |
15164 KB |
Output is correct |
10 |
Correct |
421 ms |
15228 KB |
Output is correct |
11 |
Correct |
396 ms |
15208 KB |
Output is correct |
12 |
Correct |
365 ms |
15112 KB |
Output is correct |
13 |
Correct |
357 ms |
15236 KB |
Output is correct |
14 |
Correct |
396 ms |
15192 KB |
Output is correct |
15 |
Correct |
3 ms |
5964 KB |
Output is correct |
16 |
Correct |
4 ms |
5964 KB |
Output is correct |
17 |
Correct |
3 ms |
5964 KB |
Output is correct |
18 |
Correct |
5 ms |
5964 KB |
Output is correct |
19 |
Correct |
4 ms |
5964 KB |
Output is correct |
20 |
Correct |
7 ms |
5964 KB |
Output is correct |
21 |
Correct |
92 ms |
9276 KB |
Output is correct |
22 |
Correct |
5 ms |
5964 KB |
Output is correct |
23 |
Correct |
7 ms |
5964 KB |
Output is correct |
24 |
Correct |
81 ms |
9252 KB |
Output is correct |
25 |
Correct |
73 ms |
9124 KB |
Output is correct |
26 |
Correct |
73 ms |
9368 KB |
Output is correct |
27 |
Correct |
81 ms |
9364 KB |
Output is correct |
28 |
Correct |
116 ms |
10192 KB |
Output is correct |
29 |
Correct |
733 ms |
16040 KB |
Output is correct |
30 |
Correct |
118 ms |
9560 KB |
Output is correct |
31 |
Correct |
737 ms |
16196 KB |
Output is correct |
32 |
Correct |
502 ms |
15996 KB |
Output is correct |
33 |
Correct |
492 ms |
15992 KB |
Output is correct |
34 |
Correct |
800 ms |
16000 KB |
Output is correct |
35 |
Correct |
3 ms |
5964 KB |
Output is correct |
36 |
Correct |
4 ms |
5964 KB |
Output is correct |
37 |
Correct |
72 ms |
8840 KB |
Output is correct |
38 |
Correct |
400 ms |
15828 KB |
Output is correct |
39 |
Correct |
499 ms |
15988 KB |
Output is correct |
40 |
Correct |
645 ms |
16012 KB |
Output is correct |
41 |
Correct |
731 ms |
15904 KB |
Output is correct |
42 |
Correct |
693 ms |
15920 KB |
Output is correct |
43 |
Correct |
441 ms |
15904 KB |
Output is correct |
44 |
Correct |
448 ms |
15876 KB |
Output is correct |
45 |
Correct |
418 ms |
15220 KB |
Output is correct |
46 |
Correct |
437 ms |
15876 KB |
Output is correct |
47 |
Correct |
516 ms |
16000 KB |
Output is correct |
48 |
Correct |
4 ms |
5964 KB |
Output is correct |
49 |
Correct |
3 ms |
5964 KB |
Output is correct |
50 |
Correct |
3 ms |
5964 KB |
Output is correct |
51 |
Correct |
4 ms |
5964 KB |
Output is correct |
52 |
Incorrect |
4 ms |
5964 KB |
Output isn't correct |
53 |
Halted |
0 ms |
0 KB |
- |