#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7, MM = 2e5+5;
int N, K, lz[4*MM], mi[4*MM]; vi ord1, ord2;
void pushdn(int rt){
mi[lc]+=lz[rt]; mi[rc]+=lz[rt];
lz[lc]+=lz[rt]; lz[rc]+=lz[rt]; lz[rt]=0;
}
void upd(int L, int R, int l, int r, int val, int rt){
if(r < L || l > R) return;
if(l <= L && R <= r){ mi[rt]+=val; lz[rt]+=val; return; }
if(lz[rt]) pushdn(rt);
int mid = (L+R)/2;
if(l <= mid) upd(L, mid, l, r, val, lc);
if(r > mid) upd(mid+1, R, l, r, val, rc);
mi[rt] = min(mi[lc], mi[rc]);
}
int qry(int L, int R, int rt){
if(mi[rt] > 0) return -1;
if(L==R) return L;
if(lz[rt]) pushdn(rt);
int mid = (L+R)/2;
if(mi[lc] > 0) return qry(mid+1, R, rc);
return qry(L, mid, lc);
}
vi solve(vi& r){
vi ret(N); cl(lz, 0); cl(mi, 0);
for(int i=0; i<N; i++)
upd(0, N-1, i, i, r[i], 1);
for(int i=0; i<N; i++){
int pos = qry(0, N-1, 1);
ret[pos] = i;
upd(0, N-1, pos, pos, inf, 1);
upd(0, N-1, pos-K+1, pos-1, -1, 1);
if(pos-K+1<0) upd(0, N-1, pos+N-K, N-1, -1, 1);
}
// for(int x: ret) cout << x << " ";
cout << endl;
return ret;
}
void init(int k, vi r){
r.insert(r.end(), r.begin(), r.end());
N = r.size(); K = k;
ord1 = solve(r);
for(int &x: r) x = k-1-x;
ord2 = solve(r);
}
int compare_plants(int x, int y){
if(x > y) return -compare_plants(y, x);
if(ord1[x] > ord1[y] || ord2[x+N/2] < ord2[y]) return -1;
if(ord2[x] > ord2[y] || ord1[x+N/2] < ord1[y]) return 1;
return 0;
}
//int main(){
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// int k=3; vi a={0, 1, 1, 2};
// init(k, a);
// for(int i=0; i<a.size(); i++)
// for(int j=i+1; j<a.size(); j++)
// cout << i << " vs " << j << " = " << compare_plants(i, j) << endl;
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
5 ms |
6528 KB |
Output is correct |
4 |
Correct |
5 ms |
6548 KB |
Output is correct |
5 |
Correct |
5 ms |
6528 KB |
Output is correct |
6 |
Correct |
67 ms |
9388 KB |
Output is correct |
7 |
Correct |
132 ms |
10200 KB |
Output is correct |
8 |
Runtime error |
145 ms |
25832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
5 ms |
6528 KB |
Output is correct |
4 |
Correct |
5 ms |
6528 KB |
Output is correct |
5 |
Correct |
5 ms |
6528 KB |
Output is correct |
6 |
Correct |
9 ms |
6656 KB |
Output is correct |
7 |
Correct |
93 ms |
9592 KB |
Output is correct |
8 |
Correct |
7 ms |
6656 KB |
Output is correct |
9 |
Correct |
9 ms |
6656 KB |
Output is correct |
10 |
Correct |
94 ms |
9592 KB |
Output is correct |
11 |
Correct |
87 ms |
9464 KB |
Output is correct |
12 |
Correct |
92 ms |
9720 KB |
Output is correct |
13 |
Correct |
93 ms |
9592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
5 ms |
6528 KB |
Output is correct |
4 |
Correct |
5 ms |
6528 KB |
Output is correct |
5 |
Correct |
5 ms |
6528 KB |
Output is correct |
6 |
Correct |
9 ms |
6656 KB |
Output is correct |
7 |
Correct |
93 ms |
9592 KB |
Output is correct |
8 |
Correct |
7 ms |
6656 KB |
Output is correct |
9 |
Correct |
9 ms |
6656 KB |
Output is correct |
10 |
Correct |
94 ms |
9592 KB |
Output is correct |
11 |
Correct |
87 ms |
9464 KB |
Output is correct |
12 |
Correct |
92 ms |
9720 KB |
Output is correct |
13 |
Correct |
93 ms |
9592 KB |
Output is correct |
14 |
Correct |
168 ms |
10072 KB |
Output is correct |
15 |
Runtime error |
168 ms |
25848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
81 ms |
9464 KB |
Output is correct |
4 |
Runtime error |
146 ms |
25832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
5 ms |
6528 KB |
Output is correct |
4 |
Correct |
5 ms |
6528 KB |
Output is correct |
5 |
Correct |
5 ms |
6528 KB |
Output is correct |
6 |
Correct |
7 ms |
6656 KB |
Output is correct |
7 |
Correct |
21 ms |
7296 KB |
Output is correct |
8 |
Correct |
21 ms |
7168 KB |
Output is correct |
9 |
Correct |
20 ms |
7168 KB |
Output is correct |
10 |
Correct |
22 ms |
7160 KB |
Output is correct |
11 |
Correct |
20 ms |
7168 KB |
Output is correct |
12 |
Correct |
21 ms |
7168 KB |
Output is correct |
13 |
Correct |
21 ms |
7168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
5 ms |
6528 KB |
Output is correct |
4 |
Correct |
5 ms |
6528 KB |
Output is correct |
5 |
Correct |
8 ms |
6656 KB |
Output is correct |
6 |
Runtime error |
134 ms |
25832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6528 KB |
Output is correct |
2 |
Correct |
5 ms |
6528 KB |
Output is correct |
3 |
Correct |
5 ms |
6528 KB |
Output is correct |
4 |
Correct |
5 ms |
6548 KB |
Output is correct |
5 |
Correct |
5 ms |
6528 KB |
Output is correct |
6 |
Correct |
67 ms |
9388 KB |
Output is correct |
7 |
Correct |
132 ms |
10200 KB |
Output is correct |
8 |
Runtime error |
145 ms |
25832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |