Submission #1026787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026787		NeroZein	Food Court (JOI21_foodcourt)	C++17	0 / 100	67 ms	71268 KiB

foodcourt

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

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 2e5 + 5; 
const long long INF = 1e15 + 15; 

struct node {
  long long sum, lazy, mn, mn2;
  int mnc;
};

int ptr[N];
long long tree[N];
node beats[N * 2];
long long seg[N * 2];
long long lazy[N * 2]; 

node combine(node lx, node rx) {
  node ret;
  ret.lazy = 0;
  ret.sum = lx.sum + rx.sum;
  if (lx.mn == rx.mn) {
    ret.mn = lx.mn;
    ret.mnc = lx.mnc + rx.mnc;
    ret.mn2 = min(lx.mn2, rx.mn2);
  } else if (lx.mn < rx.mn) {
    ret.mn = lx.mn;
    ret.mnc = lx.mnc;
    ret.mn2 = min(lx.mn2, rx.mn);
  } else {
    ret.mn = rx.mn;
    ret.mnc = rx.mnc;
    ret.mn2 = min(lx.mn, rx.mn2);
  }
  return ret;
}

void build_beats(int nd, int l, int r) {
  if (l == r) {
    beats[nd].mnc = 1; 
    beats[nd].mn2 = INF;
    beats[nd].lazy = beats[nd].sum = beats[nd].mn = 0;
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build_beats(nd + 1, l, mid);
  build_beats(rs, mid + 1, r); 
  beats[nd] = combine(beats[nd + 1], beats[rs]);
}

void apply_add(int nd, int l, int r, int v) {
  beats[nd].sum += (long long) (r - l + 1) * v; 
  beats[nd].mn += v; 
  if (beats[nd].mn2 != INF) {
    beats[nd].mn2 += v; 
  }
  beats[nd].lazy += v; 
}

void apply_maximize(int nd, int l, int r, int v) {
  if (beats[nd].mn >= v) {
    return;
  }
  beats[nd].sum -= (long long) beats[nd].mn * beats[nd].mnc;
  beats[nd].mn = v; 
  beats[nd].sum += (long long) beats[nd].mn * beats[nd].mnc;
}

void push_down(int nd, int l, int r) {
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  apply_add(nd + 1, l, mid, beats[nd].lazy);
  apply_add(rs, mid + 1, r, beats[nd].lazy);
  beats[nd].lazy = 0;
  apply_maximize(nd + 1, l, mid, beats[nd].mn);
  apply_maximize(rs, mid + 1, r, beats[nd].mn); 
}

void add_beats(int nd, int l, int r, int s, int e, int v) {
  if (l >= s && r <= e) {
    apply_add(nd, l, r, v);
    return; 
  }
  push_down(nd, l, r); 
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    add_beats(nd + 1, l, mid, s, e, v); 
  } else {
    if (mid < s) {
      add_beats(rs, mid + 1, r, s, e, v);       
    } else {
      add_beats(nd + 1, l, mid, s, e, v); 
      add_beats(rs, mid + 1, r, s, e, v); 
    }
  }
  beats[nd] = combine(beats[nd + 1], beats[rs]);
}

void maximize(int nd, int l, int r, int s, int e, int v) {
  if (beats[nd].mn >= v) {
    return; 
  }
  if (l >= s && r <= e && beats[nd].mn2 > v) {
    apply_maximize(nd, l, r, v);
    return; 
  }
  push_down(nd, l, r);
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    maximize(nd + 1, l, mid, s, e, v);
  } else {
    if (mid < s) {
      maximize(rs, mid + 1, r, s, e, v);
    } else {
      maximize(nd + 1, l, mid, s, e, v);
      maximize(rs, mid + 1, r, s, e, v);
    }
  }
  beats[nd] = combine(beats[nd + 1], beats[rs]);
}

long long qry_beats(int nd, int l, int r, int p) {
  if (l == r) {
    return beats[nd].sum;
  }
  push_down(nd, l, r); 
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    return qry_beats(nd + 1, l, mid, p);
  } else {
    return qry_beats(rs, mid + 1, r, p);
  }
}

void upd(int ind, int v) {
  while (ind < N) {
    tree[ind] += v;
    ind += ind & -ind;
  }
}

void upd(int l, int r, int v) {
  upd(l, v);
  upd(r + 1, -v);
}

long long qry(int ind) {
  long long ret = 0;
  while (ind) {
    ret += tree[ind];
    ind -= ind & -ind;
  }
  return ret; 
}

void build(int nd, int l, int r, vector<vector<pair<long long, int>>>& qs) {
  if (l == r) {
    if (!qs[l].empty()) {
      seg[nd] = qs[l][0].first; 
    } else {
      seg[nd] = INF;
    }
    return; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid, qs);
  build(rs, mid + 1, r, qs);
  seg[nd] = min(seg[nd + 1], seg[rs]);
}

void push(int nd, int l, int r) {
  seg[nd] += lazy[nd];
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lazy[nd + 1] += lazy[nd];
    lazy[rs] += lazy[nd]; 
  }
  lazy[nd] = 0; 
}

void upd(int nd, int l, int r, int s, int e, long long v) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    lazy[nd] = v; 
    push(nd, l, r);
    return; 
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    upd(nd + 1, l, mid, s, e, v); 
    push(rs, mid + 1, r); 
  } else {
    if (mid < s) {
      upd(rs, mid + 1, r, s, e, v);
      push(nd + 1, l, mid); 
    } else {
      upd(nd + 1, l, mid, s, e, v); 
      upd(rs, mid + 1, r, s, e, v);
    }
  }
  seg[nd] = min(seg[nd + 1], seg[rs]);
}

int get(int nd, int l, int r) {
  push(nd, l, r); 
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  push(nd + 1, l, mid);
  if (seg[nd + 1] <= 0) {
    return get(nd + 1, l, mid);
  }
  return get(rs, mid + 1, r); 
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  build_beats(0, 1, n);
  vector<vector<pair<long long, int>>> qs(m + 1);
  vector<int> type(q), lq(q), rq(q), cq(q), kq(q), a(q), b(q), ans(q);
  for (int i = 0; i < q; ++i) {
    cin >> type[i];
    if (type[i] == 1) {
      cin >> lq[i] >> rq[i] >> cq[i] >> kq[i];
      upd(lq[i], rq[i], kq[i]); 
      add_beats(0, 1, n, lq[i], rq[i], kq[i]);
    } else if (type[i] == 2) {
      cin >> lq[i] >> rq[i] >> kq[i];
      add_beats(0, 1, n, lq[i], rq[i], -kq[i]);
      maximize(0, 1, n, lq[i], rq[i], 0);
    } else {
      cin >> a[i] >> b[i];
      long long tot = qry(a[i]);
      long long cur = qry_beats(0, 1, n, a[i]);
      if (cur >= b[i]) {
        qs[a[i]].push_back({tot - (cur - b[i]), i});
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    sort(qs[i].begin(), qs[i].end());
  }
  build(0, 1, m, qs);
  for (int i = 0; i < q; ++i) {
    if (type[i] == 3) {
      cout << ans[i] << '\n';
    } 
    if (type[i] != 1) {
      continue; 
    }
    upd(0, 1, m, lq[i], rq[i], -kq[i]);
    while (seg[0] <= 0) {
      int ind = get(0, 1, m);
      ans[qs[ind][ptr[ind]].second] = cq[i]; 
      ptr[ind]++;
      if (false && ptr[ind] < (int) qs[ind].size()) {
        upd(0, 1, m, ind, ind, qs[ind][ptr[ind]].first - qs[ind][ptr[ind] - 1].first);
      } else {
        upd(0, 1, m, ind, ind, INF);
      }
    }
  }
  return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11