#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];
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){
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;
}
set < pair<int,int> > st;
set < pair<int,int> > :: iterator it;
int low , high , res , mid , l;
void add(int r,int idx){
it = st.lower_bound(make_pair(r,0));
if(it != st.end() && it->second < idx)
return;
low = 0 , high = r, res = r + 1;
while(high >= low){
mid = (low + high) / 2;
it = st.lower_bound(make_pair(mid,0));
if(it != st.end() || it->second <= idx){
res = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
it = st.lower_bound(make_pair(res,0));
while(it != st.end() && it->first <= r){
st.erase(it);
it = st.lower_bound(make_pair(res,0));
}
st.insert(make_pair(r,idx));
}
void changewaget(int n,int *arr,int r){
nxt[n] = n;
for(int i=n-1;i>=0;i--){
if(arr[i] > r)
nxt[i] = i;
else
nxt[i] = nxt[i+1];
}
l = 0;
for(int i=0;i<n;i++){
if(arr[i] > r) continue;
while(l < (int)v.size() && v[l].first <= i){
add(v[l].second.first,v[l].second.second);
l++;
}
it = st.lower_bound(make_pair(nxt[i]+1,0));
if(it != st.end())
waget[i] = min(waget[i],it->second);
}
}
void changewaget2(int n,int *arr,int r){
st.clear();
reverse(arr,arr+n);
nxt[n] = n;
for(int i=n-1;i>=0;i--){
if(arr[i] > r)
nxt[i] = i;
else
nxt[i] = nxt[i+1];
}
l = 0;
for(int i=0;i<n;i++){
if(arr[i] > r) continue;
while(l < (int)v.size() && v[l].first <= i){
add(v[l].second.first,v[l].second.second);
l++;
}
it = st.lower_bound(make_pair(nxt[i]+1,0));
if(it != st.end())
waget[n - i - 1] = min(waget[n - i - 1],it->second);
}
}
int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
build(0,n-1,1);
memset(lazy,-1,sizeof(lazy));
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);
v.push_back(make_pair(S[i],make_pair(E[i],i)));
}
sort(v.begin(),v.end());
for(int i=0;i<n;i++)
waget[i] = 1e9;
changewaget(n-1,K,R);
changewaget2(n-1,K,R);
int maxval = -1 , bestidx = -1;
for(int i=0;i<n-1;i++){
if(K[i] > R) continue;
tmp = getless(i,waget[i],n);
if(tmp > maxval){
maxval = tmp;
bestidx = i;
}
}
return bestidx;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11384 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
11500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
11736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
15896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
