이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
template<class S,auto op,auto e>
struct SegmentTree{
int size;
vector<S> tree;
SegmentTree(int sz){
size=sz;
tree.resize(size*2);
rep(i,size*2)tree[i]=e();
}
void set(int pos,S val){
pos+=size;
tree[pos]=val;
pos/=2;
while(pos>0){
tree[pos]=op(tree[pos*2],tree[pos*2+1]);
pos/=2;
}
}
S get(int pos){
return tree[pos+size];
}
S prod(int lf,int ri){
lf+=size;
ri+=size;
S ret_lf=e();
S ret_ri=e();
while(lf<ri){
if(lf%2==1){
ret_lf=op(ret_lf,tree[lf]);
lf++;
}
if(ri%2==1){
ri--;
ret_ri=op(tree[ri],ret_ri);
}
lf/=2;
ri/=2;
}
return op(ret_lf,ret_ri);
}
};
using T=pair<int,int>;
T op(T x,T y){
return {x.first+y.first,max(x.second,x.first+y.second)};
}
T e(){
return {0,0};
}
T add(T x,T y){
return {x.first+y.first,x.second+y.second};
}
int ma(int x,int y){
return max(x,y);
}
int me(){
return -1;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
SegmentTree<T, op, e> seg(N),seg2(N);
SegmentTree<int, ma, me> night(N-1);
rep(i,N){
seg.set(i,{1,1});
seg2.set(i,{1,1});
}
rep(i,N-1){
night.set(i,K[i]);
}
vector<pair<int,int>> new_se(C);
vector<int> ans(N+1);
rep(i,C){
int s=S[i],e=E[i]+1;
int ok=N,ng=-1;
while(ok-ng>1){
int mid=(ok+ng)/2;
if(seg2.prod(0,mid).second>s){
ok=mid;
}
else{
ng=mid;
}
}
int lf=ok-1;
ok=N;
ng=-1;
while(ok-ng>1){
int mid=(ok+ng)/2;
if(seg.prod(0,mid).second>=e){
ok=mid;
}
else{
ng=mid;
}
}
int ri=ok;
seg.set(lf,add(seg.get(lf),{-e+s+1,-e+s+1}));
if(lf+1<N){
seg2.set(lf+1,add(seg2.get(lf+1),{-e+s+1,-e+s+1}));
}
ri--;
if(night.prod(lf,ri)<R){
ans[lf]++;
ans[ri+1]--;
}
}
int fin=ans[0];
rep(i,N){
ans[i+1]+=ans[i];
fin=max(fin,ans[i+1]);
}
return fin;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |