제출 #362756

#제출 시각아이디문제언어결과실행 시간메모리
362756Dymo휴가 (IOI14_holiday)C++14
24 / 100
26 ms10356 KiB
#include "holiday.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" const ll maxn =2e5+10; const ll mod=1e9+7; const ll base=1e15; ll st[maxn]; ll st1[maxn]; ll val[maxn]; ll pos[maxn]; struct tk { ll n; ll l=1; ll r=0; void update(ll id,ll left,ll right,ll x,ll diff) { if (x>right||x<left) return ; if (left==right) { st[id]+=diff; st1[id]+=val[left]*diff; return ; } ll mid=(left+right)/2; update(id*2,left,mid, x, diff); update(id*2+1,mid+1, right, x, diff); st[id]=st[id*2]+st[id*2+1]; st1[id]=st1[id*2]+st1[id*2+1]; } void finit(ll n1) { l=1; r=0; init(1,1,n1); n=n1; } void init(ll id,ll left,ll right) { st[id]=0; st1[id]=0; if (left==right) return ; ll mid=(left+right)/2; init(id*2,left,mid); init(id*2+1,mid+1, right); } void ers(ll t) { update(1,1,n,t,-1); } void add(ll t) { update(1,1,n,t,1); } ll get1(ll lf,ll rt,ll x) { if (x<0) return -1e15; while (l>lf) { l--; add(pos[l]); } while (l<lf) { ers(pos[l]); l++; } while (r<rt) { r++; add(pos[r]); } while (r>rt) { ers(pos[r]); r--; } if (x>st[1]) { return st1[1]; } return get(1,1,n,x); } ll get(ll id,ll left,ll right,ll x) { if (left==right) { return val[left]*x; } ll mid=(left+right)/2; if (st[id*2+1]<x) { return get(id*2,left,mid,x-st[id*2+1])+st1[id*2+1]; } else { return get(id*2+1,mid+1,right,x); } } } man; ll ans[maxn]; void dac(ll start,ll l,ll r,ll low,ll high,ll d) { if (l>r) return ; ll mid=(l+r)/2; ll pos_best=-1; ans[mid]=-1e15; for (int i=low;i<=high;i++) { ll kc=mid-start; if (i!=start) { kc+=mid-i; } ll t=man.get1(i,mid,d-kc); if (ans[mid]<t) { ans[mid]=t; pos_best=i; } } /*if (mid==5) { cout <<ans[mid]<<" "<<pos_best<<endl; }*/ dac(start,l,mid-1,low,pos_best,d); dac(start,mid+1,r,pos_best,high,d); } ll dosth(ll start,ll n,ll d) { man.finit(n); // cout << dac(start,start,min(n,start+d),1,start,d); ll res=0; for (int i=1;i<=n;i++) { res=max(res,ans[i]); } return res; } ll findMaxAttraction(int n,int start,int d,int attraction[]) { vector<ll> vt; for (int i=0; i<n; i++) { pos[i+1]=attraction[i]; vt.pb(pos[i+1]); } sort(vt.begin(),vt.end()); vt.resize(unique(vt.begin(),vt.end())-vt.begin()); ll siz=vt.size(); for (int i=1; i<=siz; i++) { val[i]=vt[i-1]; // cout <<val[i]<<" "; } // cout <<endl; for (int i=1; i<=n; i++) { pos[i]=lower_bound(vt.begin(),vt.end(),pos[i])-vt.begin()+1; // cout <<pos[i]<<" "; } // cout <<endl; //cout <<siz<<endl; man.finit(n); start++; ll ans=dosth(start, n,d); // cout <<dosth(start,n,d)<<endl; reverse(pos+1,pos+n+1); ans=max(ans,dosth(n-start+1,n,d)); /* for (int i=1;i<=n;i++) { cout <<pos[i]<<" "; } cout <<endl; cout <<start<<endl; cout <<dosth(n-start+1,n,d)<<endl;*/ return ans; } /*int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } int t[100]; t[0]=10; t[1]=2; t[2]=20; t[3]=30; t[4]=1; cout <<findMaxAttraction(5,2,7,t)<<endl; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...