Submission #387320

#	Time	Username	Problem	Language	Result	Execution time	Memory
387320		rama_pang	Food Court (JOI21_foodcourt)	C++17	100 / 100	566 ms	42220 KiB

foodcourt

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

using lint = long long;
const lint inf = 1e18;

// Build Segment Tree over queries
// We need to simulate operations fast
// Can be done with matrix-like multiplication
// O(N + Q log Q).
//
// Matrix Multiplication:
// [a, b] [e] = [min(a + e, b + f)]
// [c, d] [f] = [min(c + e, d + f)]
//
// Identity:
// [0, inf] [head]
// [inf, 0] [tail]
//
// Push Back
// [0, inf] [head]
// [inf, K] [tail]
//
// Pop Front
// [K,   0] [head]
// [inf, 0] [tail]

struct Matrix {
  array<array<lint, 2>, 2> M;

  Matrix(lint K = 0) {
    if (K == 0) { // Identity
      M[0] = {0, inf};
      M[1] = {inf, 0};
    } else if (K > 0) { // Push Back
      M[0] = {0, inf};
      M[1] = {inf, K};
    } else if (K < 0) { // Pop Front
      M[0] = {-K,  0};
      M[1] = {inf, 0};
    }
  }

  pair<lint, lint> Get(lint head, lint tail) { // Multiply by (head, tail)
    return pair(min(M[0][0] + head, M[0][1] + tail), min(M[1][0] + head, M[1][1] + tail));
  }

  friend Matrix operator*(const Matrix &a, const Matrix &b) {
    Matrix c;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        c.M[i][j] = min(a.M[i][0] + b.M[0][j], a.M[i][1] + b.M[1][j]);
      }
    }
    return c;
  }
};

class SegTree {
 public:
  int sz;
  vector<Matrix> tree;

  SegTree(int n) {
    sz = 1; while (sz < n) sz *= 2;
    tree.assign(2 * sz, Matrix(0));
  }

  void Modify(int p, int K) {
    tree[p += sz] = Matrix(K);
    for (p /= 2; p > 0; p /= 2) {
      tree[p] = tree[p * 2 + 1] * tree[p * 2];
    }
  }

  pair<lint, lint> Query(int l, int r) { // (head, tail)
    Matrix L(0), R(0);
    for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) L = tree[l++] * L;
      if (r & 1) R = R * tree[--r];
    }
    return (R * L).Get(0, 0);
  }

  int BinarySearch(lint pos) {
    int r = 1;
    lint head = 0, tail = 0;
    while (r < sz) {
      if (pos < tree[r * 2].Get(head, tail).second) {
        r = r * 2;
      } else {
        tie(head, tail) = tree[r * 2].Get(head, tail);
        r = r * 2 + 1;
      }
    }
    tie(head, tail) = tree[r].Get(head, tail);
    assert(pos < tail);
    return r - sz;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M, Q;
  cin >> N >> M >> Q;

  vector<int> ans(Q + 1, -1);
  vector<int> color(Q + 1, -1);
  vector<vector<array<lint, 3>>> Query(N + 1);

  for (int q = 1; q <= Q; q++) {
    int T;
    cin >> T;
    if (T == 1) {
      lint L, R, K;
      cin >> L >> R >> color[q] >> K;
      Query[L - 1].push_back({0, q, K});
      Query[R].push_back({0, q, 0});
    } else if (T == 2) {
      lint L, R, K;
      cin >> L >> R >> K;
      Query[L - 1].push_back({0, q, -K});
      Query[R].push_back({0, q, 0});
    } else if (T == 3) {
      lint A, B;
      cin >> A >> B;
      Query[A - 1].push_back({1, q, B});
    }
  }

  SegTree seg(Q + 1);
  for (int S = 0; S < N; S++) { // Current shop
    for (auto [t, q, k] : Query[S]) {
      if (t == 0) {
        seg.Modify(q, k);
      } else if (t == 1) {
        auto [head, tail] = seg.Query(0, q);
        lint ans_pos = head + k - 1;
        ans[q] = ans_pos >= tail ? 0 : color[seg.BinarySearch(ans_pos)];
      }
    }
  }

  for (int q = 1; q <= Q; q++) {
    if (ans[q] != -1) {
      cout << ans[q] << '\n';
    }
  }
  return 0;
}

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