제출 #933228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933228		shenfe1	휴가 (IOI14_holiday)	C++17	23 / 100	1421 ms	46444 KiB

holiday

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using namespace std;

#define F first
#define S second
#define ll long long
// #define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound
#define y1 yy
#define ppb pop_back
#define ull unsigned ll

const int MAX=5e5+55;
const int inf=1e9;
const int N=2e5;
const int C=331;
const int C1=431;
const int mod=1e9+9;
const int mod1=1e9+9;
#include "holiday.h"

struct node{
  int val,cnt;
  node(){
    val=cnt=0;
  }
};

int n;
int a[MAX];
int pos[MAX];
int st;

node t[4*MAX];

void update(int v,int tl,int tr,int pos,int x){
  if(tl==tr){
    if(x==-1){
      t[v].val=0;
      t[v].cnt=0;
    }
    else{
      t[v].val=x;
      t[v].cnt=1;
    }
    return;
  }
  ll tm=(tl+tr)/2;
  if(pos<=tm)update(2*v,tl,tm,pos,x);
  else update(2*v+1,tm+1,tr,pos,x);
  t[v].val=t[2*v].val+t[2*v+1].val;
  t[v].cnt=t[2*v].cnt+t[2*v+1].cnt;
}

ll get(ll v,ll tl,ll tr,ll cnt){
  if(tl==tr){
    if(cnt>0)return t[v].val;
    return 0;
  }
  ll tm=(tl+tr)/2;
  if(t[2*v].cnt>=cnt)return get(2*v,tl,tm,cnt);
  else return t[2*v].val+get(2*v+1,tm+1,tr,cnt-t[2*v].cnt);
}

ll dpR[3][MAX];
ll optR[3][MAX];

void calcR(ll l,ll r,ll L,ll R,ll k){
  if(l>r)return;
  ll m=(l+r)/2;
  optR[k][m]=L;
  for(ll i=L;i<=R;i++){
    update(1,1,n,pos[i],a[i]);
    ll cnt=(m-k*(i-st));
    ll cur=0;
    if(cnt>=0){
      if(t[1].cnt<=cnt){
        cur=t[1].val;
      }
      else{
        cur=get(1,1,n,cnt);
      }
    }
    // cout<<m<<" "<<cnt<<" "<<cur<<"\n";
    if(cur>dpR[k][m]){
      dpR[k][m]=cur;
      optR[k][m]=i;
    }
    // cout<<L<<" "<<R<<" "<<cnt<<" "<<cur<<"\n";
  }
  // cout<<k<<" "<<m<<" "<<dpR[k][m]<<" "<<L<<" "<<R<<" "<<get(1,1,n,1)<<"\n";
  // return;
  for(ll i=L;i<=R;i++){
    update(1,1,n,pos[i],-1);
  }
  if(l==r)return;
  calcR(l,m-1,L,optR[k][m],k);
  for(ll i=L;i<=optR[k][m];i++){
    update(1,1,n,pos[i],a[i]);
  }
  calcR(m+1,r,optR[k][m],R,k);
  for(ll i=L;i<=R;i++){
    update(1,1,n,pos[i],-1);
  }
}

ll dpL[3][MAX];
ll optL[3][MAX];

void calcL(ll l,ll r,ll L,ll R,ll k){
  if(l>r)return;
  ll m=(l+r)/2;
  // cout<<m<<" "<<L<<" "<<R<<"\n";
  optL[k][m]=R;
  // cout<<m<<"\n";
  for(ll i=R;i>=L;i--){
    update(1,1,n,pos[i],a[i]);
    ll cnt=(m-k*(st-1-i));
    // cout<<i<<" "<<cnt<<"\n";
    ll cur=0;
    if(cnt>=0){
      if(t[1].cnt<=cnt){
        cur=t[1].val;
      }
      else{
        cur=get(1,1,n,cnt);
      }
    }
    if(cur>dpL[k][m]){
      dpL[k][m]=cur;
      optL[k][m]=i;
    }
  }
  for(ll i=L;i<=R;i++){
    update(1,1,n,pos[i],-1);
  }
  if(l==r)return;
  // calcL(m+1,r,L,optL[k][m],k);
  calcL(l,m-1,optL[k][m],R,k);
  for(ll i=R;i>=optL[k][m];i--){
    update(1,1,n,pos[i],a[i]);
  }
  calcL(m+1,r,L,optL[k][m],k);
  for(ll i=L;i<=R;i++){
    update(1,1,n,pos[i],-1);
  }
}

ll findMaxAttraction(int N,int start,int d,int attraction[]) {

  n=N;
  for(ll i=1;i<=n;i++)a[i]=attraction[i-1];
  start++;
  st=start;
  vector<pii> vec;
  for(ll i=1;i<=n;i++){
    // cout<<a[i]<<" "<<i<<"\n";
    vec.pb({a[i],i});
  }
  sort(all(vec));
  reverse(all(vec));
  for(ll i=0;i<sz(vec);i++){
    pos[vec[i].S]=i+1;
  }
  // mem(dpR,-1);
  // mem(dpL,-1);
  calcR(1,d,start,n,1);
  calcR(1,d,start,n,2);
  calcL(1,d,1,start-1,1);
  calcL(1,d,1,start-1,2);
  ll ans=0;
  for(ll i=0;i<=d;i++){
    // cout<<i<<" "<<dpR[1][i]<<"\n";
    // cout<<i<<" "<<dpR[2][i]<<" "<<dpL[1][d-i-1]<<"\n";
    // cout<<dpR[2][i]<<"\n";
    ans=max(ans,dpR[2][i]+dpL[1][d-i-1]);
    ans=max(ans,dpR[1][i]+dpL[2][d-i-2]);
  }
  return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53