Submission #966092

#TimeUsernameProblemLanguageResultExecution timeMemory
966092hirayuu_ojJousting tournament (IOI12_tournament)C++17
0 / 100
83 ms3624 KiB
#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-1){ 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...