이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1<<17;
int n, k;
struct SegmentTree {
int tree[maxn<<1], lazy[maxn<<1];
void flush(int node, int i, int j) {
if(!lazy[node]) return;
if(i != j) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
tree[node] += lazy[node];
lazy[node] = 0;
}
void build(int node, int i, int j, const vector<int>& r) {
if(i == j) return (void)(tree[node] = r[i]);
int m = (i+j) >> 1;
build(node<<1, i, m, r);
build(node<<1|1, m+1, j, r);
tree[node] = min(tree[node<<1], tree[node<<1|1]);
}
int find(int l, int r) {
if(l <= r) return find(1, 0, n-1, l, r);
int p1 = find(1, 0, n-1, l, n-1);
if(p1 != -1) return p1;
return find(1, 0, n-1, 0, r);
}
int find(int node, int i, int j, int l, int r) {
flush(node, i, j);
if(tree[node] > 0) return -1;
if(i == j) return i;
int m = (i+j) >> 1;
int p1 = find(node<<1, i, m, l, r);
if(p1 != -1) return p1;
return find(node<<1|1, m+1, j, l, r);
}
void upd(int l, int r, int v) {
if(l <= r) upd(1, 0, n-1, l, r, v);
else upd(1, 0, n-1, l, n-1, v), upd(1, 0, n-1, 0, r, v);
}
void upd(int node, int i, int j, int l, int r, int v) {
flush(node, i, j);
if(i > r || j < l) return;
if(i >= l && j <= r) {
lazy[node] = v;
flush(node, i, j);
return;
}
int m = (i+j) >> 1;
upd(node<<1, i, m, l, r, v);
upd(node<<1|1, m+1, j, l, r, v);
tree[node] = min(tree[node<<1], tree[node<<1|1]);
}
} seg;
int ordem[maxn];
void init(int K, std::vector<int> r) {
n = (int)(r.size());
k = K;
seg.build(1, 0, n-1, r);
for(int i = 0; i < n; i++) {
int mn = seg.find(0, n-1);
mn = seg.find((mn - k + 1 + n) % n, mn); // se tiver algum outro cara maximo para a frente dele mas ele estiver olhando pra mim
ordem[mn] = i;
seg.upd((mn - k + 1 + n) % n, mn, -1); // removo 1 de todo mundo antes de mim
seg.upd(1, 0, n-1, mn, mn, 0x3f3f3f3f);
}
}
int compare_plants(int x, int y) {
return ordem[x] < ordem[y] ? 1 : -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |