제출 #245774

#제출 시각아이디문제언어결과실행 시간메모리
245774gs18115휴가 (IOI14_holiday)C++14
7 / 100
83 ms54216 KiB
#include"holiday.h" #include<iostream> #include<vector> #include<algorithm> #define ep emplace #define eb emplace_back #define fi first #define se second #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair<int,int>pi; typedef pair<ll,ll>pl; const int inf=1e9+7; const ll INF=1e18+7; struct node { int cnt; ll sum; int l,r; node(){sum=0;cnt=l=r=0;} }tree[2222222]; int tct; void upd(int&n,int s,int e,int x,int p) { tree[++tct]=tree[n]; n=tct; tree[n].cnt++; tree[n].sum+=p; if(s==e) return; int m=s+(e-s)/2; if(x>m) upd(tree[n].r,m+1,e,x,p); else upd(tree[n].l,s,m,x,p); return; } ll query(int l,int r,int k) { if(k<=0) return 0; if(k>=tree[r].cnt-tree[l].cnt) return tree[r].sum-tree[l].sum; node&ln=tree[tree[l].r]; node&rn=tree[tree[r].r]; if(k>=rn.cnt-ln.cnt) return(rn.sum-ln.sum)+query(tree[l].l,tree[r].l,k-(rn.cnt-ln.cnt)); return query(tree[l].r,tree[r].r,k); } int rt[100010]; int n,st,d; ll ans; void dnc1(int s,int e,int as,int ae) { if(s>e) return; int m=s+(e-s)/2; int mxi=-1; ll cans=-1; for(int i=as;i<=ae;i++) { ll cur=query(rt[i-1],rt[m],d-(st+m-i*2)); if(cur>cans) cans=cur,mxi=i; } ans=max(ans,cans); dnc1(s,m-1,as,mxi); dnc1(m+1,e,mxi,ae); return; } void dnc2(int s,int e,int as,int ae) { if(s>e) return; int m=s+(e-s)/2; int mxi=-1; ll cans=-1; for(int i=as;i<=ae;i++) { ll cur=query(rt[m-1],rt[i],d-(i*2-st-m)); if(cur>cans) cans=cur,mxi=i; } ans=max(ans,cans); dnc2(s,m-1,as,mxi); dnc2(m+1,e,mxi,ae); return; } long long int findMaxAttraction(int n,int start,int d,int attraction[]) { ::n=n; ::st=start+1; ::d=d; cin>>n>>st>>d; vector<int>v(n); for(int i=0;i<n;i++) v[i]=attraction[i]; vector<int>cv=v; sort(all(cv)); cv.erase(unique(all(cv)),cv.end()); int m=cv.size(); v.insert(v.begin(),0); for(int i=0;i++<n;) upd(rt[i]=rt[i-1],1,m,upper_bound(all(cv),v[i])-cv.begin(),v[i]); dnc1(st,min(n,st+d-1),1,st); dnc2(max(1,st-d+1),st,st,n); return ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...