#include "plants.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
template<typename T = pii, typename S = ll>
struct lazy_segment_tree{
int N, log;
T valINF;
S lazyINF;
vector<T> node;
vector<S> lazy;
lazy_segment_tree(int n, T valINF_, S lazyINF_): valINF(valINF_), lazyINF(lazyINF_){
N = 1;
log = 0;
while(N <= n){
N *= 2;
log++;
}
node.resize(2*N, valINF);
lazy.resize(2*N, lazyINF);
}
void init(vector<T> a){
rep(i,0,a.size()) node[i+N] = a[i];
per(i,N-1,1) node[i] = compare(node[i*2], node[i*2+1]);
}
void range_add(S val, ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(r <= a || b <= l) return;
if(a <= l && r <= b){
addition(node[now], val);
eval(now);
return;
}
range_add(val, a, b, now*2, l, (l+r)/2);
range_add(val, a, b, now*2+1, (l+r)/2, r);
node[now] = compare(node[now*2], node[now*2+1]);
}
T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
eval(now);
if(r <= a || b <= l) return valINF;
if(a <= l && r <= b) return node[now];
T L = calc(a, b, now*2, l, (l+r)/2);
T R = calc(a, b, now*2+1, (l+r)/2, r);
return compare(L,R);
}
void update(ll idx, T val){
ll now = idx+N;
per(i,log,0){
eval(now>>i);
}
node[now] = val;
now /= 2;
while(now){
eval(now*2);
eval(now*2+1);
node[now] = compare(node[now*2], node[now*2+1]);
now /= 2;
}
}
void eval(ll now){
addition(node[now], lazy[now]);
if(now < N){
addition(lazy[now*2], lazy[now]);
addition(lazy[now*2+1], lazy[now]);
}
lazy[now] = lazyINF;
}
void addition(T &a, S b){
a.first += b;
}
void addition(S &a, S b){
a += b;
}
T compare(T a, T b){
return std::min(a, b);
}
};
ll N;
vi height;
void init(int k, std::vector<int> r) {
N = r.size();
assert(2*k > N);
lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
{
vector<pii> a(N);
rep(i,0,N) a[i] = mp(r[i], i);
seg.init(a);
}
height.resize(N);
ll now = N;
std::set<ll> cand;
std::set<ll> top;
auto check = [&](ll idx){
auto itr = cand.lower_bound(idx);
itr--;
ll right = idx+k-1;
right -= N;
if(*itr <= right) return true;
else return false;
};
while(true){
while(true){
auto el = seg.calc(0,N);
if(el.first) break;
ll i = el.second;
cand.insert(i);
cand.insert(i-N);
cand.insert(i+N);
if(check(i)) top.insert(i);
if(cand.size() > 3){
ll upper = *cand.upper_bound(i);
if(upper >= N) upper -= N;
if(top.count(upper)){
if(!check(upper)) top.erase(upper);
}
}
seg.update(i,mp(inf, 0));
}
if(cand.empty()) break;
assert(top.size() == 1);
ll t = *top.begin();
height[t] = now--;
{
ll l = t-k+1;
ll r = t;
if(0 <= l) seg.range_add(-1, l, r);
else{
seg.range_add(-1, 0, r);
seg.range_add(-1, N+l, N);
}
}
cand.erase(t);
cand.erase(t-N);
cand.erase(t+N);
top.erase(t);
if(cand.empty()) continue;
ll upper = *cand.upper_bound(t);
if(upper >= N) upper -= N;
if(check(upper)) top.insert(upper);
}
/*while((seg.calc(0,N)).first == 0){
vi idx;
while(true){
auto el = seg.calc(0,N);
if(el.first) break;
idx.pb(el.second);
seg.update(el.second, mp(inf, 0));
}
if(idx.size() == 1){
height[idx[0]] = now--;
ll l = idx[0]-k+1;
ll r = idx[0];
if(0 <= l) seg.range_add(-1, l, r);
else{
seg.range_add(-1, 0, r);
seg.range_add(-1, N+l, N);
}
continue;
}
assert(idx.size() == 2);
if(idx[0] > idx[1]) std::swap(idx[0], idx[1]);
if(idx[1] < idx[0]+k){
idx[0] = now--;
idx[1] = now--;
}
else{
idx[1] = now--;
idx[0] = now--;
}
rep(i,0,2){
ll l = idx[i]-k+1;
ll r = idx[i];
if(0 <= l) seg.range_add(-1, l, r);
else{
seg.range_add(-1, 0, r);
seg.range_add(-1, N+l, N);
}
}
}*/
/*rep(i,0,N) cout << height[i] << " ";
cout << ln;*/
}
int compare_plants(int x, int y) {
if(height[x] < height[y]) return -1;
else return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
