Submission #736883

#	Time	Username	Problem	Language	Result	Execution time	Memory
736883		cig32	Holiday (IOI14_holiday)	C++17	24 / 100	5103 ms	28296 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct segtree_basic {
  struct node {
    int lazyval, mi, ma, sum; char lazytag;
    int len; // not changing
  };
  int stok;
  vector<node> st;
  void bu(int l, int r, int idx) {
    st[idx].lazyval = st[idx].mi = st[idx].ma = st[idx].sum = 0;
    st[idx].lazytag = '?';
    st[idx].len = r - l + 1;
    if(l == r) {
      return;
    }
    int mid = (l + r) >> 1;
    bu(l, mid, 2*idx+1);
    bu(mid+1, r, 2*idx+2);
  }
  void push_down(int idx) {
    if(st[idx].lazytag == '?') return;
    if(st[idx].lazytag == ':') {
      st[2*idx+1].lazyval = st[idx].lazyval;
      st[2*idx+1].mi = st[idx].lazyval;
      st[2*idx+1].ma = st[idx].lazyval;
      st[2*idx+1].sum = st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = ':';
 
      st[2*idx+2].lazyval = st[idx].lazyval;
      st[2*idx+2].mi = st[idx].lazyval;
      st[2*idx+2].ma = st[idx].lazyval;
      st[2*idx+2].sum = st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = ':';
 
    }
    else {
      st[2*idx+1].lazyval += st[idx].lazyval;
      st[2*idx+1].mi += st[idx].lazyval;
      st[2*idx+1].ma += st[idx].lazyval;
      st[2*idx+1].sum += st[idx].lazyval * st[2*idx+1].len;
      st[2*idx+1].lazytag = (st[2*idx+1].lazytag == ':' ? ':' : '+');
 
      st[2*idx+2].lazyval += st[idx].lazyval;
      st[2*idx+2].mi += st[idx].lazyval;
      st[2*idx+2].ma += st[idx].lazyval;
      st[2*idx+2].sum += st[idx].lazyval * st[2*idx+2].len;
      st[2*idx+2].lazytag = (st[2*idx+2].lazytag == ':' ? ':' : '+');
    }
    st[idx].lazytag = '?';
    st[idx].lazyval = 0;
  }
  void push_up(int idx) {
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
    st[idx].sum = st[2*idx+1].sum + st[2*idx+2].sum;
  }
  void u1(int l, int r, int constl, int constr, int idx, int val) { // range := v
    if(l <= constl && constr <= r) {
      st[idx].lazyval = val;
      st[idx].mi = val;
      st[idx].ma = val;
      st[idx].sum = val * st[idx].len;
      st[idx].lazytag = ':';
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u1(l, r, constl, mid, 2*idx+1, val);
    else {
      u1(l, r, constl, mid, 2*idx+1, val);
      u1(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
 
  void u2(int l, int r, int constl, int constr, int idx, int val) { // range += v
    if(l <= constl && constr <= r) {
      st[idx].lazyval += val;
      st[idx].mi += val;
      st[idx].ma += val;
      st[idx].sum += val * st[idx].len;
      st[idx].lazytag = (st[idx].lazytag == ':' ? ':' : '+');
      return;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) u2(l, r, constl, mid, 2*idx+1, val);
    else {
      u2(l, r, constl, mid, 2*idx+1, val);
      u2(l, r, mid+1, constr, 2*idx+2, val);
    }
    push_up(idx);
  }
  int qu7(int l, int r, int constl, int constr, int idx, int val) { // last at most v
    if(l <= constl && constr <= r) {
      if(st[idx].mi > val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        push_down(idx);
        if(st[2*idx+2].mi <= val) constl = mid+1, idx = 2*idx + 2;
        else constr = mid, idx = 2*idx + 1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid < l || r < constl) return qu7(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid + 1) return qu7(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchild = qu7(l, r, mid+1, constr, 2*idx+2, val);
      if(rchild != -1) return rchild;
      return qu7(l, r, constl, mid, 2*idx+1, val);
    }
  }
  public:
  void resize(int k) {
    st.resize(4*k + 10);
    stok = k;
    bu(0, k, 0);
  }
  void range_assign(int l, int r, int v) { u1(l, r, 0, stok, 0, v); }
  void range_add(int l, int r, int v) { u2(l, r, 0, stok, 0, v); }
  int query_lastAtMost(int l, int r, int v) { return qu7(l, r, 0, stok, 0, v); }
};
const int MAXN = 1e5 + 5;
int a[MAXN];
int n_, start_, d_;
int f(int thres) {
  int ans = 0;
  int n = n_, start = start_, d = d_;
  int ps[n+1];
  ps[0] = 0;
  for(int i=1; i<=n; i++) ps[i] = ps[i-1] + (a[i] >= thres);
  int ps2[n+1];
  ps2[0] = 0;
  for(int i=1; i<=n; i++) ps2[i] = ps2[i-1] + (a[i] >= thres ? a[i] : 0);
  segtree_basic stb;
  stb.resize(n);
  for(int i=1; i<=n; i++) stb.range_assign(i, i, i+ps[i]);
  for(int i=max(1ll, start-d); i<=start; i++) {
    int x = d - (start-i);
    int idx = stb.query_lastAtMost(i, n, x+i+ps[i-1]);
    if(idx >= start) ans = max(ans, ps2[idx] - ps2[i-1]);
  }
  start = n+1 - start;
  for(int i=1; i<=n; i++) ps[i] = ps[i-1] + (a[n+1-i] >= thres);
  for(int i=1; i<=n; i++) ps2[i] = ps2[i-1] + (a[n+1-i] >= thres ? a[n+1-i] : 0);
  for(int i=1; i<=n; i++) stb.range_assign(i, i, i+ps[i]);
  for(int i=max(1ll, start-d); i<=start; i++) {
    int x = d - (start-i);
    int idx = stb.query_lastAtMost(i, n, x+i+ps[i-1]);
    if(idx >= start) ans = max(ans, ps2[idx] - ps2[i-1]);
  }
  return ans;
}
long long findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
  n_ = n;
  start_ = start + 1;
  d_ = d;
  set<int> st;
  for(int i=0; i<n; i++) st.insert(attraction[i]);
  for(int i=1; i<=n; i++) a[i] = attraction[i-1];
  vector<int> vt;
  for(int ss: st) vt.push_back(ss);
  int m = vt.size();
  int ans = 0;
  for(int i=0; i<m; i++) ans = max(ans, f(vt[i]));
  return ans;
}

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