Submission #1052145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052145		awu	Ants and Sugar (JOI22_sugar)	C++17	0 / 100	4064 ms	87380 KiB

sugar

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
 
#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [&](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii =  pair<int, int>;
 
const ll inf = 1ll << 60;
 
template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  return out << "(" << p.f << ", " << p.s << ")";
}
template <typename T, typename = decltype(begin(declval<T>()))>
typename enable_if<!is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T x) {
  string dlm = "";
  out << "{";
  for(auto i : x) {
    out << dlm << i;
    dlm = ", ";
  }
  return out << "}";
}
 
struct segnode {
  signed tl, tr;
  int v, lz;
  segnode *lc, *rc;
  void push() {
    signed tm = (tl + tr) / 2;
    if(!lc) lc = new segnode{tl, tm};
    if(!rc) rc = new segnode{tm, tr};
    if(!lz) return;
    v += lz;
    lc->lz += lz;
    rc->lz += lz;
    lz = 0;
  }
  void update(int i, int x) {
    if(tl + 1 == tr) {
      v = x;
      lz = 0;
      return;
    }
    push();
    int tm = (tl + tr) / 2;
    if(i < tm) lc->update(i, x);
    else rc->update(i, x);
    lc->push();
    rc->push();
    v = min(lc->v, rc->v);
  }
  void add(int ul, int ur, int x) {
    if(ul >= tr || ur <= tl) return;
    if(ul <= tl && ur >= tr) {
      lz += x;
      return;
    }
    push();
    lc->add(ul, ur, x);
    rc->add(ul, ur, x);
    lc->push();
    rc->push();
    v = min(lc->v, rc->v);
  }
  int get(int i) {
    push();
    if(tl + 1 == tr) return v;
    int tm = (tl + tr) / 2;
    if(i < tm) return lc->get(i);
    return rc->get(i);
  }
  int walk(int ql, int qr, int x) { // walk for leftmost i such that v[i] < x
    if(v >= x) return -1;
    if(ql >= tr || qr <= tl) return -1;
    if(ql <= tl && qr >= tr) return walk_helper(x);
    push();
    int res = lc->walk(ql, qr, x);
    if(res != -1) return res;
    return rc->walk(ql, qr, x);
  }
  int walk_helper(int x) {
    if(tl + 1 == tr) return tl;
    push();
    lc->push();
    if(lc->v < x) return lc->walk_helper(x);
    return rc->walk_helper(x);
  }
};
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n = 1e9;
  int q, l; cin >> q >> l;
  map<int, int> asp, ssp; // spares
  asp[inf] = -1;
  ssp[inf] = -1;
  segnode lst{0, (int)5e8 + 5}, rst{0, (int)5e8 + 5};
  int ans = 0;
  while(q--) {
    int t, x, a; cin >> t >> x >> a;
    assert((t + x) % 2 == 0);
    x /= 2;
    // debug(asp);
    // debug(ssp);
    if(t == 1) {
      while(true) {
        int v = min(a, ssp[x]);
        ans += v;
        a -= v;
        ssp[x] -= v;
        if(ssp[x] == 0) ssp.erase(x);
        lst.add(x, x + 1, v);
        v = min(a, ssp[x + 1]);
        ans += v;
        a -= v;
        ssp[x + 1] -= v;
        if(ssp[x + 1] == 0) ssp.erase(x + 1);
        rst.add(x, x + 1, v);
        if(a > lst.get(x + 1)) {
          int dif = a - lst.get(x + 1);
          // debug(x);
          asp[x] += dif;
          a -= dif;
        }
        if(a == 0) break;
        int i = lst.walk(x + 1, inf, a);
        assert(i != -1);
        i = min(i, ssp.lower_bound(x)->f);
        lst.add(x + 1, i, -a);
        rst.add(x, i - 1, a);
        x = i - 1;
      }
    } else {
      while(true) {
        int v = min(a, asp[x - 1]);
        ans += v;
        a -= v;
        asp[x - 1] -= v;
        if(asp[x - 1] == 0) asp.erase(x - 1);
        rst.add(x - 1, x, v);
        v = min(a, asp[x]);
        ans += v;
        a -= v;
        asp[x] -= v;
        if(asp[x] == 0) asp.erase(x);
        lst.add(x, x + 1, v);
        if(a > rst.get(x)) {
          int dif = a - rst.get(x);
          ssp[x] += dif;
          a -= dif;
        }
        if(a == 0) break;
        // debug(x);
        int i = rst.walk(x, inf, a);
        // debug(i);
        assert(i != -1);
        i = min(i, asp.lower_bound(x)->f);
        rst.add(x, i, -a);
        lst.add(x, i, a);
        x = i;
      }
    }
    cout << ans << '\n';
  }
}

Compilation message (stderr)

sugar.cpp: In function 'int main()':
sugar.cpp:102:7: warning: unused variable 'n' [-Wunused-variable]
  102 |   int n = 1e9;
      |       ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52