#include <bits/stdc++.h>
using namespace std;
struct info{
int mx;
bool marked;
int sum;
info(){}
info(int _mx, bool _marked, int _sum): mx(_mx), marked(_marked), sum(_sum){}
};
vector<info> ST;
vector<int> V;
vector<int> alive;
void build(int p, int L, int R){
if(L == R){
ST[p].mx = L;
ST[p].marked = 0;
ST[p].sum = alive[L];
return;
}
int mid = (L+R)/2;
build(p*2, L, mid);
build(p*2+1, mid+1, R);
if(V[ST[p*2].mx] > V[ST[p*2+1].mx]) ST[p].mx = ST[p*2].mx;
else ST[p].mx = ST[p*2+1].mx;
ST[p].sum = ST[p*2].sum + ST[p*2+1].sum;
}
void push(int p, int L, int R){
if(ST[p].marked == 0) return;
if(L != R){
ST[p*2].marked = 1;
ST[p*2+1].marked = 1;
ST[p*2].sum = 0;
ST[p*2+1].sum = 0;
}
ST[p].marked = 0;
ST[p].sum = 0;
}
int getMax(int p, int L, int R, int i, int j){
push(p, L, R);
if(i > R || j < L) return -1;
if(i <= L && R <= j) return ST[p].mx;
int mid = (L+R)/2;
int idx1 = getMax(p*2, L, mid, i, j);
int idx2 = getMax(p*2+1, mid+1, R, i, j);
if(idx1 == -1) return idx2;
if(idx2 == -1) return idx1;
if(V[idx1] > V[idx2]) return idx1;
return idx2;
}
int getIth(int pos, int N){
int p = 1;
int sum = 0;
int low = 0;
int high = N-1;
int ret = -1;
while(low < high){
push(p, low, high);
int mid = low + (high-low)/2;
int sumLeft = ST[p*2].sum;
if(sum + sumLeft >= pos){
p*=2;
high = mid;
ret = mid;
}else{
sum += sumLeft;
p = p*2+1;
low = mid+1;
}
}
return ret;
}
void update(int p, int L, int R, int i, int j){
push(p, L, R);
if(i > R || j < L) return;
if(i <= L && R <= j){
ST[p].sum = 0;
if(L != R){
ST[p*2].marked = 1;
ST[p*2+1].marked = 1;
}
ST[p*2].marked = 0;
return;
}
int mid = (L+R)/2;
update(p*2, L, mid, i, j);
update(p*2+1, mid+1, R, i, j);
ST[p].sum = ST[p*2].sum + ST[p*2+1].sum;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
ST.assign(N*4+1, {});
V.assign(N, 0);
alive.assign(N, 1);
E[0]--;
for(int i = 0; i < N; i++) V[i] = K[i];
build(1, 0, N-1);
unordered_map<int, int> mp;
for(int c = 0; c < C; c++){
int start = S[c]+1;
int end = E[c]+1;
// get startesimo e endesimo elemento
int i = getIth(start, N);
int j = getIth(end, N);
// cerco il massimo
int mxIdx = getMax(1, 0, N-1, i, j);
mp[V[mxIdx]]++;
// cancello quelli attorno idx
if(i <= mxIdx-1)
update(1, 0, N-1, i, mxIdx-1);
if(mxIdx+1 <= j)
update(1, 0, N-1, mxIdx+1, j);
}
// cercare in mp il valore più piccolo di R che vince di più;
int cnt = 0;
for(auto m : mp){
if(m.first < R)
cnt = max(cnt, m.second);
}
return cnt;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
7508 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
