Submission #1150076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150076		mychecksedad	Holiday (IOI14_holiday)	C++20	100 / 100	436 ms	12900 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int dpf[N], dpg[N], n, st, A[N], POS[N], num[N];
ll valf[N], valg[N], T[N];
int ptr;
vector<pii> val;
void build(int sz){
  for(int j = 0; j <= 4*sz; ++j) num[j]=T[j]=0;
}

void upd(int l, int r, int p, int k, bool f){
  if(l == r){
    if(f)
      num[k] = 1, T[k] = val[l].ff;
    else
      num[k] = 0, T[k] = 0;
    return;
  }
  int m = l+r>>1;
  if(p <= m) upd(l, m, p, k<<1, f);
  else upd(m+1, r, p, k<<1|1, f);
  num[k] = num[k<<1] + num[k<<1|1];
  T[k] = T[k<<1] + T[k<<1|1];
}

ll get(int l, int r, int tot, int k){
  if(num[k] == 0 || tot == 0) return 0ll;
  int m = l + r >> 1;
  if(tot >= num[k]){
    return T[k];
  }
  if(l==r) return 0ll;
  if(num[k<<1|1] <= tot){
    return get(l, m, tot - num[k<<1|1], k<<1) + T[k<<1|1];
  }
  return get(m+1, r, tot, k<<1|1);
}

void calcf(int pos, int ql, int qr){
  dpf[pos] = ql;
  // cout << ptr << "f\n";
  for(; ptr < ql; ++ptr){
    upd(0, n-1, POS[ptr], 1, 1);
  }

  for(; ptr > ql; --ptr){
    upd(0, n-1, POS[ptr-1], 1, 0);
  }
  ll best = 0;
  for(; ptr <= qr; ++ptr){
    if(pos - (ptr - st) < 0) break;
    upd(0, n-1, POS[ptr], 1, 1);
    ll f = get(0, n-1, pos - (ptr - st), 1); //cout << num[1] << ' ' << ptr << ' ' << f << ' ' << POS[ptr] << ' ' << pos - ptr + st << '\n';
    if(f > best) best = f, dpf[pos] = ptr;
  }
  valf[pos] = best;
}
void calcg(int pos, int ql, int qr){
  dpg[pos] = qr;
  for(; ptr > qr; --ptr){
    upd(0, n-1, POS[ptr], 1, 1);
  }

  for(; ptr < qr; ++ptr){
    upd(0, n-1, POS[ptr+1], 1, 0);
  }
  ll best = 0;
  for(; ptr >= ql; --ptr){
    if(pos - (st - ptr) < 0) break;
    upd(0, n-1, POS[ptr], 1, 1);
    ll f = get(0, n-1, pos - (st - ptr), 1);
    if(f > best) best = f, dpg[pos] = ptr;
  }
  valg[pos] = best;
}
void f(int l, int r, int ql, int qr){
  if(r < l) return;
  int mid = l+r>>1;
  calcf(mid, ql, qr);
  if(l == r) return;
  f(l, mid - 1, ql, dpf[mid]);
  f(mid + 1, r, dpf[mid], qr);
}
void g(int l, int r, int ql, int qr){
  if(r < l) return;
  int mid = l+r>>1;
  calcg(mid, ql, qr);
  if(l == r) return;
  g(l, mid - 1, dpg[mid], qr);
  g(mid + 1, r, ql, dpg[mid]);
}

long long int findMaxAttraction(int nn, int start, int d, int AA[]) {
  st = start;
  n = nn;
  for(int i = 1; i <= n; ++i){
    A[i-1]=AA[i-1];
    val.pb({A[i-1],i-1});
  }
  sort(all(val));
  for(int i = 1; i <= n; ++i){
    POS[val[i-1].ss] = i - 1;
  }


  build(n);
  ptr = start;
  f(0, d, start, n - 1);
  if(start == 0){
    return valf[d];
  }
  build(n);
  ptr = start - 1;  
  g(1, d, 0, start - 1);
  ll ans = 0;
  for(int i = 0; i <= d; ++i){
    int go = dpf[i];
    if(d - i - (go - start) > 0)
      ans = max(ans, valf[i] + valg[d - i - (go - start)]);
    ans = max(ans, valf[i]);
    // cout << i << ' ' << valf[i] << '\n';
  }
  for(int i = 1; i <= d; ++i){
    int go = dpg[i];
    if(d - i - (start - go) > 0)
      ans = max(ans, valg[i] + valf[d - i - (start - go)]);
    ans = max(ans, valg[i]);
    if(i < d) ans = max(ans, valg[i] + A[start]);
  }
  return ans;
}

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