Submission #694137

#	Time	Username	Problem	Language	Result	Execution time	Memory
694137		erray	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	1265 ms	71964 KiB

sugar

// author: erray
#undef DEBUG 
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

  struct node {
    //0 merge
    //1 max
    array<array<long long, 2>, 2> x{};
    array<long long, 2> tag{};
    void modify(int type, long long d) {
      if (type == 0) {
        //start max
        x[1][0] += d, x[1][1] += d;
        tag[type] += d;
      } else if (type == 1) {
        //end max
        x[0][1] += d, x[1][1] += d;
        tag[type] += d;      
      } else if (type == 2) {
        //start merge
        x[0][0] += d, x[0][1] += d; 
      } else if (type == 3) {
        //end merge
        x[0][0] += d, x[1][0] += d;      
      } else {
        //whole 
        x[0][0] += d, x[0][1] += d, x[1][0] += d, x[1][1] += d;
      }
    } 
  };
  node operator+(node l, node r) {
    l.x[1][1] = max(0LL, l.x[1][1]);
    r.x[1][1] = max(0LL, r.x[1][1]);
    node res;
    res.x[0][0] = max(l.x[0][1] + r.x[1][0], l.x[0][0] + r.x[0][0]);
    res.x[1][1] = max(l.x[1][1] + r.x[1][1], l.x[1][0] + r.x[0][1]);
    res.x[0][1] = max(l.x[0][1] + r.x[1][1], l.x[0][0] + r.x[0][1]);
    res.x[1][0] = max(r.x[1][0] + l.x[1][1], l.x[1][0] + r.x[0][0]);
    return res;
  }

struct SegTree {
  int n;
  vector<node> tree;
  #define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
  void push(int v, int l, int r) {
    def;
    for (int i = 0; i < 2; ++i) {
      if (tree[v].tag[i] != 0) {
        tree[v + 1].modify(i, tree[v].tag[i]);
        tree[rv].modify(i, tree[v].tag[i]);        
        tree[v].tag[i] = 0;
      }
    }
  }
  void modify(int v, int l, int r, int ll, int rr, int type, int x) {
    if (l >= ll && rr >= r) {
      tree[v].modify(type, x);
      debug(v, l, tree[v].x);
      return;
    }        
    def;
    push(v, l, r);
    //debug(v, v + 1, rv);
    if (ll <= mid) {
      modify(v + 1, l, mid, ll, rr, type, x);
    }                 	
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, type, x);
    }
    tree[v] = tree[v + 1] + tree[rv];
    debug(v, l, r, tree[v].x);  
  }
  SegTree(int _n) : n(_n) {
    tree.resize((n << 1) - 1);
  }
  long long get() {
    return max(0LL, tree[0].x[1][1]);
  }
  void modify(int l, int r, int type, int x) {
     assert(0 <= l && l <= r && r < n && 0 <= type && type < 4);
     debug(l, r, type, x);
     modify(0, 0, n - 1, l, r, type, x);
  }
  void modify(int p, int x) {
    assert(0 <= p && p < n);
    debug(p, x);
    modify(0, 0, n - 1, p, p, 4, x);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int Q, L;
  cin >> Q >> L;
  vector<int> T(Q), X(Q), A(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> T[i] >> X[i] >> A[i];
  }
  debug(X);
  vector<int> cords;
  for (int i = 0; i < Q; ++i) {
    if (T[i] == 1) {
      cords.push_back(X[i]);
    }
  }
  sort(cords.begin(), cords.end());
  int s = int(unique(cords.begin(), cords.end()) - cords.begin());
  cords.resize(s);
  if (s == 0) {
    for (int i = 0; i < Q; ++i) {
      cout << 0 << '\n';
    }
    return 0;
  }
  if (s == 1) {
    long long V = 0;
    long long U = 0;
    for (int i = 0; i < Q; ++i) {
      if (T[i] == 1) {
        V += A[i];
      } else if (abs(cords[0] - X[i]) <= L) {
        U += A[i];
      }
      cout << min(V, U) << '\n';
    }
    return 0;
  }
  auto LB = [&](int x) {
    return int(lower_bound(cords.begin(), cords.end(), x) - cords.begin());
  };
  debug(cords);

  SegTree st(s);
  long long total = 0;
  for (int q = 0; q < Q; ++q) {
    debug(q, total);
    if (T[q] == 1) {
      total += A[q]; 
      st.modify(LB(X[q]), A[q]);
    } else {
      int id = LB(X[q]);
      debug(id, A[q]);
      if (id < s && cords[id] == X[q]) {
        st.modify(LB(X[q]), -A[q]);
      } else if (id == s || (id > 0 && X[q] <= cords[id - 1] + L))  {
        st.modify(id - 1, id - 1, 3, -A[q]);
      } else {
        st.modify(id, id, 2, -A[q]);        
      }
      {
        int l = LB(X[q] - L);
        int r = LB(X[q]) - 1;
        debug(l, r);
        if (l <= r) {
          st.modify(l, r, 1, -A[q]);   
        }
      }
      {
         int r = LB(X[q] + L + 1) - 1;
         int l = LB(X[q] + 1);
         debug(l, r);
         if (l <= r) {
           st.modify(l, r, 0, -A[q]);
         }
      }
    }
    debug(total, st.get());
    cout << total - st.get() << '\n';
  }
}

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