#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int INF=1e9;
const int MX=4e5+100;
int n, k;
vi r;
int h[MX];
struct Seg {
ii SEG[MX*4]; int LAZY[MX*4];
void build(const vi& f, int p=0, int l=0, int r=n-1) {
LAZY[p] = 0;
if(l == r) {
SEG[p] = {f[l], l};
return;
}
int m=(l+r)/2;
build(f,p*2+1,l,m);
build(f,p*2+2,m+1,r);
SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
}
void add(int i, int j, int v, int lazy=0, int p=0, int l=0, int r=n-1) {
LAZY[p] += lazy;
SEG[p].fi += lazy;
if(j < l || i > r) return;
if(i <= l && j >= r) {
SEG[p].fi += v;
LAZY[p] += v;
return;
}
int m=(l+r)/2;
add(i,j,v,LAZY[p],p*2+1,l,m);
add(i,j,v,LAZY[p],p*2+2,m+1,r);
LAZY[p] = 0;
SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
}
void addRound(int i, int j, int v) {
if(i >= n) i-=n, j-=n;
if(j < n) {
add(i,j,v);
} else {
add(i,n-1,v);
add(0,j-n,v);
}
}
} seg1, seg2;
int ans0[MX];
void fill0() {
int x=0, y=n-1;
RE(i,n) ans0[i] = 0;
set<int> s; s.insert(h[x]);
REP(i,x+1,y+1) {
if(s.empty()) break;
int p = *s.begin();
if(p < h[i]) {
s.insert(h[i]);
ans0[i] = -1;
}
if(i >= k-1) s.erase(h[i-k+1]);
}
s.clear(); s.insert(h[x]);
REP(i,x+1,y+1) {
if(s.empty()) break;
int p = *(--s.end());
if(p > h[i]) {
s.insert(h[i]);
ans0[i] = 1;
}
if(i >= k-1) s.erase(h[i-k+1]);
}
REV(i,x+1,y+1) {
if(s.empty()) break;
int p = *s.begin();
if(p < h[i]) {
s.insert(h[i]);
ans0[i] = -1;
}
s.erase(h[i+k-1]);
}
s.clear(); s.insert(h[x]);
REV(i,x+1,y+1) {
if(s.empty()) break;
int p = *(--s.end());
if(p > h[i]) {
s.insert(h[i]);
ans0[i] = 1;
}
s.erase(h[i+k-1]);
}
}
void init(int _k, vi _r) {
k = _k; r = _r;
n = r.size();
seg1.build(r);
seg2.build(vi(n,0));
RE(i,n) {
while(seg1.SEG[0].fi == k-1) {
int x = seg1.SEG[0].se;
seg1.add(x,x,-INF);
seg2.add(x,x,1);
seg2.addRound(x+1,x+k-1,-1);
}
int x = seg2.SEG[0].se;
seg2.add(x,x,-INF);
seg2.addRound(x+1,x+k-1,1);
seg1.addRound(x+n-k+1,x+n-1,1);
h[x] = h[x+n] = i;
}
fill0();
return;
}
int comp(int x, int y) {
if(y < x) y += n;
if(h[x] < h[y]) {
set<int> s; s.insert(h[x]);
REP(i,x+1,y+1) {
if(s.empty()) break;
int p = *s.begin();
if(p < h[i]) {
s.insert(h[i]);
}
if(i >= k-1) s.erase(h[i-k+1]);
}
if(s.count(h[y])) return -1;
return 0;
} else {
set<int> s; s.insert(h[x]);
REP(i,x+1,y+1) {
if(s.empty()) break;
int p = *(--s.end());
if(p > h[i]) {
s.insert(h[i]);
}
if(i >= k-1) s.erase(h[i-k+1]);
}
if(s.count(h[y])) return 1;
return 0;
}
}
int compare_plants(int x, int y) {
if(x == 0) {
return ans0[y];
} else if(n <= 300) {
int res = comp(x,y);
if(res != 0) return res;
res = comp(y,x);
return -res;
} else {
if(h[x] < h[y]) return -1;
else return 1;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25600 KB |
Output is correct |
2 |
Correct |
16 ms |
25344 KB |
Output is correct |
3 |
Correct |
15 ms |
25344 KB |
Output is correct |
4 |
Correct |
15 ms |
25344 KB |
Output is correct |
5 |
Correct |
15 ms |
25344 KB |
Output is correct |
6 |
Correct |
117 ms |
28280 KB |
Output is correct |
7 |
Incorrect |
127 ms |
29304 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
25344 KB |
Output is correct |
2 |
Correct |
15 ms |
25344 KB |
Output is correct |
3 |
Correct |
15 ms |
25344 KB |
Output is correct |
4 |
Correct |
15 ms |
25344 KB |
Output is correct |
5 |
Correct |
17 ms |
25336 KB |
Output is correct |
6 |
Correct |
20 ms |
25472 KB |
Output is correct |
7 |
Correct |
108 ms |
28664 KB |
Output is correct |
8 |
Incorrect |
30 ms |
25472 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
25344 KB |
Output is correct |
2 |
Correct |
15 ms |
25344 KB |
Output is correct |
3 |
Correct |
15 ms |
25344 KB |
Output is correct |
4 |
Correct |
15 ms |
25344 KB |
Output is correct |
5 |
Correct |
17 ms |
25336 KB |
Output is correct |
6 |
Correct |
20 ms |
25472 KB |
Output is correct |
7 |
Correct |
108 ms |
28664 KB |
Output is correct |
8 |
Incorrect |
30 ms |
25472 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25344 KB |
Output is correct |
2 |
Correct |
15 ms |
25344 KB |
Output is correct |
3 |
Incorrect |
87 ms |
28408 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
25472 KB |
Output is correct |
2 |
Correct |
15 ms |
25344 KB |
Output is correct |
3 |
Incorrect |
15 ms |
25344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
25344 KB |
Output is correct |
2 |
Correct |
15 ms |
25344 KB |
Output is correct |
3 |
Incorrect |
15 ms |
25344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
25600 KB |
Output is correct |
2 |
Correct |
16 ms |
25344 KB |
Output is correct |
3 |
Correct |
15 ms |
25344 KB |
Output is correct |
4 |
Correct |
15 ms |
25344 KB |
Output is correct |
5 |
Correct |
15 ms |
25344 KB |
Output is correct |
6 |
Correct |
117 ms |
28280 KB |
Output is correct |
7 |
Incorrect |
127 ms |
29304 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |