이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using namespace __gnu_pbds;
using pii = pair<int,int>;
using piii = pair<int,pair<int,int>>;
#define N 100005
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> s;
tree<piii,null_type,less<piii>,rb_tree_tag,tree_order_statistics_node_update> q;
pair<int,int> seg[N];
int dp[N],ans;
vector<int> op[N];
int val(int l,int r){
if(l>r)return 0;
if(l)return dp[r]-dp[l-1];
return dp[r];
}
int ch(int l,int r,int m){
return val(l,m-1)+val(m,r-1);
}
int GetBestPosition(int n,int c,int R,int *K,int *S,int *E) {
int i,l,r,mid;
for(i=0;i<n;i++)s.insert({i,i});
for(i=0;i<c;i++){
auto l=s.find_by_order(S[i]),r=s.find_by_order(E[i]);
seg[i]={(*l).first,(*r).second};
r++;
while(l!=r)s.erase(l++);
s.insert(seg[i]);
op[seg[i].first].push_back(i+1);
op[seg[i].second+1].push_back(-i-1);
}
for(i=0;i<n-1;i++){
if(i)dp[i]+=dp[i-1];
dp[i]+=K[i]>R;
}
for(i=0;i<n;i++){
for(auto id:op[i]){
if(id>0)q.insert({id-1,seg[id-1]});
else q.erase({-id-1,seg[-id-1]});
}
l=0,r=((int)q.size())-1;
while(l<=r){
mid=(l+r)/2;
auto it=q.find_by_order(mid);
if(!ch((*it).second.first,(*it).second.second,i))ans=max(ans,mid+1),l=mid+1;
else r=mid-1;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |