#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);
assert(N <= 5000);
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;
while(true){
vi idx;
while(true){
ll i = min_element(all(r))-r.begin();
if(r[i]) break;
r[i] = 1e9;
idx.pb(i);
}
if(idx.empty()) break;
sort(all(idx));
ll top = 0;
rep(i,1,idx.size()){
ll r = idx[i]+k-1;
if(r < N) continue;
r -= N;
if(idx[i-1] <= r){
assert(top == 0);
top = i;
}
}
height[idx[top]] = now--;
rep(i,0,idx.size()){
if(i != top){
r[idx[i]] = 0;
continue;
}
ll nidx = idx[i];
rep(j,1,k){
nidx--;
if(nidx < 0) nidx += N;
r[nidx]--;
}
}
}
/*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);
}
}
}*/
}
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 |
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 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
4 ms |
444 KB |
Output is correct |
| 7 |
Correct |
95 ms |
5096 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
4 ms |
468 KB |
Output is correct |
| 10 |
Correct |
97 ms |
5188 KB |
Output is correct |
| 11 |
Execution timed out |
4086 ms |
5096 KB |
Time limit exceeded |
| 12 |
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 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
4 ms |
444 KB |
Output is correct |
| 7 |
Correct |
95 ms |
5096 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
4 ms |
468 KB |
Output is correct |
| 10 |
Correct |
97 ms |
5188 KB |
Output is correct |
| 11 |
Execution timed out |
4086 ms |
5096 KB |
Time limit exceeded |
| 12 |
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 |
1 ms |
212 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 |
1 ms |
256 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 |
340 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
