Submission #1106002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106002		VinhLuu	Holiday (IOI14_holiday)	C++17	100 / 100	413 ms	9664 KiB

holiday

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second

#include "holiday.h"

using namespace std;

typedef pair<int,int> pii;
const int N = 1e5 + 5;

int n, S, K;
ll a[N];

ll st[N << 2], T[N << 2];
vector<ll> rrh;
int m, b[N];

void update(int i,int l,int r,int u,int x,int t){
  if(l > r || r < u || u < l) return;
  if(l == r){
    T[i] += t;
    st[i] += x * t;
    return;
  }
  int mid = (l + r) / 2;
  update(i << 1, l, mid, u, x, t);
  update(i << 1|1, mid + 1, r, u, x, t);
  st[i] = st[i << 1] + st[i << 1|1];
  T[i] = T[i << 1] + T[i << 1|1];
}

ll wr, ret;

int query(int i,int l,int r,int u){
  if(l > r || r < u || u < l) return 0;
  if(l == r) return st[i];
  int mid = (l + r) / 2;
  return query(i << 1, l, mid, u) + query(i << 1|1, mid + 1, r, u);
}

void get(int i,int l,int r){
  if(!wr) return;

  if(l == r){
    if(!T[i]) return;
    ret += min(wr, T[i]) * (st[i] / T[i]);
    wr -= min(wr, T[i]);
    return;
  }

  if(T[i] <= wr){
    wr -= T[i];
    ret += st[i];
    return;
  }

  int mid = (l + r) / 2;
  if(T[i << 1|1] <= wr){
    wr -= T[i << 1|1];
    ret += st[i << 1|1];
    if(wr) get(i << 1, l, mid);
  }else{
    get(i << 1|1, mid + 1, r);
  }
}


void pre(){
  for(int i = 1; i <= n; i ++) rrh.push_back(a[i]);
  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());
  m = (int)rrh.size();
  for(int i = 1; i <= n; i ++) b[i] = lower_bound(all(rrh), a[i]) - rrh.begin() + 1;

}

namespace AC{

  ll ans = 0;
  int le, ri, we;
  void dfs(int l,int r,int pl,int pr){
    if(l > r) return;
    int mid = (l + r) / 2;
    while(we < mid){
      we++;
//      cerr << we << " addrrr\n";
      update(1, 1, m, b[we], a[we], 1);
    }
    while(we > mid){
//      cerr << we << " subrrr\n";
      update(1, 1, m, b[we], a[we], -1);
      we--;
    }
//    cerr << mid << " " << pl << " " << pr << " " << le << " " << ri << " t\n";
    while(le > pl){
      le--;
//      cerr << le << " addl\n";
      update(1, 1, m, b[le], a[le], 1);
    }

    while(le < pl){
      update(1, 1, m, b[le], a[le], -1);
//      cerr << le << " subl\n";
      le++;
    }
//    cerr << mid << " " << l << " " << r << " " << pl << " " << pr << " " << le << " " << ri << " " << we << " e\n";
//     << " " << le << " " << ri << " " <<we << " " << mid<< " y\n";
    ll tmp = 0, pos = pr;
    while(le <= pr){
      wr = K - min(mid - S, S - le) - (mid - le);
      if(wr >= 0){
        ret = 0;
        int last = wr;
        get(1, 1, m);
//        cerr << last << " " << le << " " << ret << " k\n";
//        for(int i = 1; i <= m; i ++) cerr << query(1, 1, m, i) << " ";
//        cerr << "\n";
        if(ret > tmp){
          tmp = ret;
          pos = le;
        }
      }
//      cerr << le << " sub\n";
      update(1, 1, m, b[le], a[le], -1);
      le++;
    }
//    cerr << tmp << " " << pos << " ptptp\n";
    ans = max(ans, tmp);
    dfs(l, mid - 1, pl, pos);
    dfs(mid + 1, r, pos, pr);
  }
  ll solve(){
    ans = 0;
    for(int i = S; i <= n; i ++){
      update(1, 1, m, b[i], a[i], 1);
      wr = K - (i - S);
      if(wr < 0) continue;
      ret = 0;
      get(1, 1, m);
      ans = max(ans, ret);
    }
    for(int i = S; i <= n; i ++) update(1, 1, m, b[i], a[i], -1);
    we = S;
//    cerr << we << " add\n";
    update(1, 1, m, b[S], a[S], 1);


    if(1 < S){
      int mk = -1;
      for(int i = S; i <= n; i ++){
        wr = K - min(S - (S - 1), i - S) - (i - (S - 1));
        if(wr < 0) break;
        mk = i;
      }
      if(mk == -1) return ans;
      le = 1, ri = 1;
      for(int i = 1; i < S; i ++) update(1, 1, m, b[i], a[i], 1);
      dfs(S, mk, 1, S - 1);
    }
    return ans;
  }
}

ll findMaxAttraction(int _n, int start, int d, int attraction[]) {
  n = _n;
  S = start + 1;
  K = d;
  for(int i = 0; i < n; i ++) a[i + 1] = attraction[i];
  pre();
  return AC :: solve();
}

//#define lpv

#ifdef lpv

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  int _n, start, d;
  int attraction[100000];
  int i, n_s;
  n_s = scanf("%d %d %d", &_n, &start, &d);
  for (i = 0 ; i < _n; ++i) {
    n_s = scanf("%d", &attraction[i]);
  }
  printf("%lld\n", findMaxAttraction(_n, start, d,  attraction));
  return 0;
}


#endif // lpv

Compilation message (stderr)

holiday.cpp: In function 'void AC::dfs(int, int, int, int)':
holiday.cpp:117:13: warning: unused variable 'last' [-Wunused-variable]
  117 |         int last = wr;
      |             ^~~~

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