#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define X first
#define Y second
#define sep ' '
const int MAXN = (1 << 18);
const int LOG = 18;
int n , m , r , ans[MAXN] , fen[MAXN] , nxt[MAXN] , val[MAXN] , dpl[MAXN] , dpr[MAXN],fen2[MAXN];
vector<int> vec[MAXN];
vector<pair<pii , pii>> Q[MAXN];
void add(int x , int val){
for(x++ ; x < MAXN ; x += x & -x) fen[x] += val;
}
int get(int x){
int ans = 0;
for(int i = (1 << (LOG - 1)) ; i ; i >>= 1){
if(fen[ans + i] <= x){
ans += i;
x -= fen[ans];
}
}
return ans;
}
void update(int x , int val){
for(x += 2 ; x < MAXN ; x += x & -x) fen2[x] += val;
}
int query(int x){
int ans = 0;
for(x += 2 ; x ; x -= x & -x) ans += fen2[x];
return ans;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
n = N; m = C; r = R;
for(int i = 0 ; i < n - 1 ; i++){
val[i] = K[i];
nxt[i] = i + 1;
add(i , 1);
}
add(n - 1 , 1);
nxt[n - 1] = n;
for(int i = 0 ; i < m ; i++){
int l = S[i] , r = E[i];
int cur = get(l) , tmp = cur;
for(int j = 0 ; j < r - l + 1 ; j++){
add(cur , -1);
cur = nxt[cur];
}
nxt[tmp] = cur;
add(tmp , 1);
vec[tmp].push_back(cur - 1);
// cout << tmp << sep << cur - 1 << endl;
}
//assert(fen[MAXN / 2] == 1);
dpl[0] = -1;
for(int i = 1 ; i < n ; i++){
dpl[i] = dpl[i - 1];
if(val[i - 1] > r) dpl[i] = i - 1;
}
dpr[n - 1] = n - 1;
for(int i = n - 2 ; i >= 0 ; i--){
dpr[i] = dpr[i + 1];
if(val[i] > r) dpr[i] = i;
}
for(int i = 0 ; i < n ; i++){
if(dpl[i] >= 0) Q[dpl[i]].push_back({{i , -1} , {i - 1 , dpr[i]}});
Q[i].push_back({{i , 1} , {i - 1 , dpr[i]}});
}
for(int i = 0 ; i < n ; i++){
// cout << i << sep << dpl[i] << sep << dpr[i] << endl;
for(int j : vec[i]) update(j , 1);
for(auto &j : Q[i]){
ans[j.X.X] += j.X.Y * (query(j.Y.Y) - query(j.Y.X));
}
}
int res = 0;
for(int i = 0 ; i < n ; i++){
if(ans[i] > ans[res]) res = i;
}
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
12780 KB |
Output is correct |
2 |
Correct |
10 ms |
12780 KB |
Output is correct |
3 |
Correct |
10 ms |
12780 KB |
Output is correct |
4 |
Correct |
10 ms |
12780 KB |
Output is correct |
5 |
Correct |
10 ms |
12780 KB |
Output is correct |
6 |
Correct |
10 ms |
12780 KB |
Output is correct |
7 |
Correct |
10 ms |
12780 KB |
Output is correct |
8 |
Correct |
12 ms |
12780 KB |
Output is correct |
9 |
Correct |
10 ms |
12780 KB |
Output is correct |
10 |
Correct |
10 ms |
12780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12780 KB |
Output is correct |
2 |
Correct |
13 ms |
13292 KB |
Output is correct |
3 |
Correct |
11 ms |
13292 KB |
Output is correct |
4 |
Correct |
13 ms |
13292 KB |
Output is correct |
5 |
Correct |
14 ms |
13420 KB |
Output is correct |
6 |
Correct |
13 ms |
13292 KB |
Output is correct |
7 |
Correct |
13 ms |
13292 KB |
Output is correct |
8 |
Correct |
13 ms |
13292 KB |
Output is correct |
9 |
Correct |
12 ms |
13312 KB |
Output is correct |
10 |
Correct |
14 ms |
13292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
46 ms |
17772 KB |
Output is correct |
2 |
Correct |
85 ms |
22756 KB |
Output is correct |
3 |
Correct |
47 ms |
20444 KB |
Output is correct |
4 |
Correct |
83 ms |
23268 KB |
Output is correct |
5 |
Correct |
83 ms |
22756 KB |
Output is correct |
6 |
Correct |
80 ms |
22932 KB |
Output is correct |
7 |
Correct |
80 ms |
23140 KB |
Output is correct |
8 |
Correct |
82 ms |
23140 KB |
Output is correct |
9 |
Correct |
44 ms |
20844 KB |
Output is correct |
10 |
Correct |
51 ms |
21612 KB |
Output is correct |