Submission #1190560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190560		tch1cherin	Ants and Sugar (JOI22_sugar)	C++20	100 / 100	3741 ms	313460 KiB

sugar

#include <bits/stdc++.h>
using namespace std;

constexpr long long INF = 1e18;

void chmax(long long& a, long long b) {
  a = a > b ? a : b;
}

struct segment_tree {
  struct node {
    long long DP[2][2], DP_small[2][2][3];
    long long alt_tag = 0, small_tag = 0;
    
    node() {
      for (int x = 0; x < 2; x++) {
        for (int y = 0; y < 2; y++) {
          if (x == y) {
            DP[x][y] = 0;
            for (int z = 0; z < 3; z++) {
              DP_small[x][y][z] = 0;
            }
          } else {
            DP[x][y] = -INF;
            for (int z = 0; z < 3; z++) {
              DP_small[x][y][z] = -INF;
            }
          }
        }
      }
    }
  };

  node merge(node a, node b) {
    node result;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          result.DP[i][k] = max(result.DP[i][k], a.DP[i][j] + b.DP[j][k]);
          for (int na = 0; na < 3; na++) {
            for (int nb = 0; na + nb < 3; nb++) {
              chmax(result.DP_small[i][k][na + nb], a.DP_small[i][j][na] + b.DP_small[j][k][nb]);
            }
          }
        }
      }
    }
    return result;
  }

  int size;
  vector<node> tree;
  
  segment_tree(int n) {
    size = 1;
    while (size < n) {
      size *= 2;
    }
    node neutral;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        neutral.DP[i][j] = 0;
        for (int cnt = 0; cnt < 3; cnt++) {
          neutral.DP_small[i][j][cnt] = (cnt == int(i == 1 && j == 0) ? 0 : -INF);
        }
      }
    }
    tree.assign(size * 2, neutral);
    for (int i = size - 1; i > 0; i--) {
      tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
  }

  void alt_apply(int x, long long value) {
    for (int i = 0; i < 2; i++) {
      tree[x].DP[i][i ^ 1] += value * (i == 0 ? -1 : +1);
      for (int n = 0; n < 3; n++) {
        tree[x].DP_small[i][i ^ 1][n] += value * (i == 0 ? -1 : +1);
      }
    }
    tree[x].alt_tag += value;
  }

  void small_apply(int x, long long value) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int n = 0; n < 3; n++) {
          tree[x].DP_small[i][j][n] += n * value;
        }
      }
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        tree[x].DP[i][j] = -INF;
        for (int n = 0; n < 3; n++) {
          tree[x].DP[i][j] = max(tree[x].DP[i][j], tree[x].DP_small[i][j][n]);
        }
      }
    }
    tree[x].small_tag += value;
  }

  void propagate(int x) {
    if (tree[x].alt_tag != 0) {
      alt_apply(x * 2, tree[x].alt_tag);
      alt_apply(x * 2 + 1, tree[x].alt_tag);
      tree[x].alt_tag = 0;
    }
    if (tree[x].small_tag != 0) {
      small_apply(x * 2, tree[x].small_tag);
      small_apply(x * 2 + 1, tree[x].small_tag);
      tree[x].small_tag = 0;
    }
  }

  void alt_update(int l, int r, int value, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      alt_apply(x, value);
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      alt_update(l, r, value, x * 2, lx, mid);
      alt_update(l, r, value, x * 2 + 1, mid, rx);
      tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }
  }

  void alt_update(int l, int r, int value) {
    alt_update(l, r, value, 1, 0, size);
  }

  void small_update(int l, int r, int value, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return;
    } else if (lx >= l && rx <= r) {
      small_apply(x, value);
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      small_update(l, r, value, x * 2, lx, mid);
      small_update(l, r, value, x * 2 + 1, mid, rx);
      tree[x] = merge(tree[x * 2], tree[x * 2 + 1]);
    }
  }

  void small_update(int l, int r, int value) {
    small_update(l, r, value, 1, 0, size);
  }
  
  pair<node, bool> query(int l, int r, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return {{}, false};
    } else if (lx >= l && rx <= r) {
      return {tree[x], true};
    } else {
      propagate(x);
      int mid = (lx + rx) / 2;
      auto [left_node, left_exists] = query(l, r, x * 2, lx, mid);
      auto [right_node, right_exists] = query(l, r, x * 2 + 1, mid, rx);
      if (left_exists && right_exists) {
        return {merge(left_node, right_node), true};
      } else if (left_exists) {
        return {left_node, true};
      } else {
        return {right_node, true};
      }
    }
  } 
 
  long long query(int l, int r) {
    return query(l, r, 1, 0, size).first.DP[0][0];
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  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];
  }
  vector<int> diff;
  for (int i = 0; i < Q; i++) {
    diff.push_back(X[i]);
    diff.push_back(X[i] + 1);
  }
  sort(diff.begin(), diff.end());
  diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
  int K = int(diff.size());
  segment_tree DS(K);
  long long ants = 0;
  for (int i = 0; i < Q; i++) {
    if (T[i] == 1) {
      int pos = upper_bound(diff.begin(), diff.end(), X[i]) - diff.begin();
      DS.alt_update(pos, K, A[i]);
      ants += A[i];
    } else {
      int lpos = upper_bound(diff.begin(), diff.end(), X[i] - L) - diff.begin();
      int rpos = upper_bound(diff.begin(), diff.end(), X[i] + L) - diff.begin();
      DS.small_update(lpos, rpos, -A[i]);
      DS.alt_update(rpos, K, -A[i]);
    }
    cout << ants - DS.query(0, K) << "\n";
  }
}

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