#include <bits/stdc++.h>
using namespace std;
const int N = 100010 , LOG = 19;
int tmp , lazy[4 * N] , seg[4 * N] , waget[N] , nxt[N] , seg3[4 * N];
vector< pair<int,pair<int,int> > > v;
vector< int > seg2[4 * N];
inline void fix(int s,int e,int idx){
if(lazy[idx] == -1)
return;
seg[idx] = lazy[idx] * (e - s + 1);
if(s != e)
lazy[idx*2] = lazy[idx*2+1] = lazy[idx];
lazy[idx] = -1;
}
int build(int s,int e,int idx){
seg3[idx] = 1e9;
if(s == e) return seg[idx] = 1;
return seg[idx] = build(s,(s+e)/2,idx*2) + build((s+e)/2+1,e,idx*2+1);
}
int getsum(int s,int e,int idx,int l,int r){
fix(s,e,idx);
if(s > r || e < l) return 0;
if(s >= l && e <= r) return seg[idx];
return getsum(s,(s+e)/2,idx*2,l,r) + getsum((s+e)/2+1,e,idx*2+1,l,r);
}
int update(int s,int e,int idx,int l,int r,int val){
fix(s,e,idx);
if(s > r || e < l) return seg[idx];
if(s >= l && e <= r){
lazy[idx] = val;
fix(s,e,idx);
return seg[idx];
}
return seg[idx] = update(s,(s+e)/2,idx*2,l,r,val) + update((s+e)/2+1,e,idx*2+1,l,r,val);
}
int lower_bound_on_seg(int val,int n){
int low = 0 , high = n - 1, res = n , mid , cur;
while(high >= low){
mid = ((low + high) >> 1);
cur = getsum(0,n-1,1,0,mid) - 1;
if(cur >= val){
res = mid;
high = mid - 1;
}
else
low = mid + 1;
}
return res;
}
void update2(int s,int e,int idx,int l,int r,int val){
if(s > r || e < l)
return ;
if(s >= l && e <= r){
seg2[idx].push_back(val);
return;
}
update2(s,(s+e)/2,idx*2,l,r,val);
update2((s+e)/2+1,e,idx*2+1,l,r,val);
}
int getless(int idx,int val,int n){
int s = 0 ,e = n -1 , mid = (s + e) / 2 , res = 0 , node = 1;
while(true){
res += lower_bound(seg2[node].begin(),seg2[node].end(),val) - seg2[node].begin();
if(s == e)
break;
mid = (s + e) / 2;
if(idx > mid){
s = mid + 1;
node = node * 2 + 1;
}
else{
e = mid;
node = node * 2;
}
}
return res;
}
void update3(int s,int e,int idx,int l,int r,int val){
if(s > r || e < l)
return;
if(s >= l && e <= r){
seg3[idx] = min(seg3[idx],val);
return;
}
update3(s,(s+e)/2,idx*2,l,r,val);
update3((s+e)/2+1,e,idx*2+1,l,r,val);
}
int getmin(int idx,int n){
int s = 0 ,e = n -1 , mid = (s + e) / 2 , res = 1e9 , node = 1;
while(true){
res = min(res,seg3[node]);
if(s == e)
break;
mid = (s + e) / 2;
if(idx > mid){
s = mid + 1;
node = node * 2 + 1;
}
else{
e = mid;
node = node * 2;
}
}
return res;
}
int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
build(0,n-1,1);
memset(lazy,-1,sizeof(lazy));
nxt[n-1] = n - 1;
for(int i=n-2;i>=0;i--){
if(K[i] > R)
nxt[i] = i;
else
nxt[i] = nxt[i+1];
}
for(int i=0;i<C;i++){
S[i] = lower_bound_on_seg(S[i],n);
E[i] = lower_bound_on_seg(E[i],n);
update(0,n-1,1,S[i]+1,E[i],0);
update2(0,n-1,1,S[i],E[i],i);
if(nxt[S[i]] <= E[i] - 1){
update3(0,n-1,1,S[i],E[i],i);
}
}
sort(v.begin(),v.end());
int maxval = -1 , bestidx = -1;
for(int i=0;i<n-1;i++){
tmp = getless(i,getmin(i,n),n);
if(tmp > maxval){
maxval = tmp;
bestidx = i;
}
}
return bestidx;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
11256 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
11368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
11424 KB |
Output is correct |
| 2 |
Correct |
34 ms |
12052 KB |
Output is correct |
| 3 |
Correct |
13 ms |
12052 KB |
Output is correct |
| 4 |
Correct |
27 ms |
12196 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
12196 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
221 ms |
15236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
