Submission #1255516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255516		LucaLucaM	Food Court (JOI21_foodcourt)	C++20	0 / 100	1097 ms	5556 KiB

foodcourt

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

struct Update {
  int type, l, r, c, k;
};  

struct Query {
  int A, B, index, indexupdates, answer;
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;

  std::vector<Update> U;
  std::vector<Query> Q;

  U.push_back(Update{});
  for (int i = 1; i <= q; i++) {
    int type;
    std::cin >> type;
    if (type == 1) {
      int l, r, c, k;
      std::cin >> l >> r >> c >> k;
      U.push_back({type, l, r, c, k});
    } else if (type == 2) {
      int l, r, k;
      std::cin >> l >> r >> k;
      U.push_back({type, l, r, 0, k});
    } else {
      int A, B;
      std::cin >> A >> B;
      Q.push_back({A, B, (int) Q.size(), (int) U.size() - 1, 0});
    }
  }
  
  auto query1 = [&](int p, int t) {
    int ret = 0;
    for (int i = 1; i <= t; i++) {
      if (U[i].l <= p && p <= U[i].r) {
        if (U[i].type == 1) {
          ret += U[i].k;
        } else {
          ret = std::max(0, ret - U[i].k);
        }
      }
    }
    return ret;
  };

  U.push_back(Update{1, 1, n, 0, (int) 1e9});

  auto query2 = [&](int p, int l, int r) {
    int cur = 0;
    for (int i = l; i <= r; i++) {
      if (U[i].type == 2 && U[i].l <= p && p <= U[i].r) {
        cur -= U[i].k;
      }
    }
    return cur;
  }; 

  for (int jump = (1 << 3); jump > 0; jump >>= 1) {
    std::sort(Q.begin(), Q.end(), [&](Query a, Query b) {
      return std::min(a.answer + jump, a.indexupdates) < std::min(b.answer + jump, b.indexupdates);
    });
    int ptr = 0;
    for (auto &[A, B, index, indexupdates, answer] : Q) {
      int newAnswer = std::min(answer + jump, indexupdates);
      while (ptr < newAnswer) {
        ptr++;
      }
      if (query1(A, newAnswer) + query2(A, newAnswer + 1, indexupdates) < B) {
        answer = newAnswer;
      }
    }
  }
  
  std::sort(Q.begin(), Q.end(), [](Query a, Query b) {
    return a.index < b.index;
  });
  
  for (auto i : Q) {
    if (i.answer < i.indexupdates) {
      i.answer++;
      std::cout << U[i.answer].c << '\n';
    } else {
      std::cout << "0\n";
    }
  }
  
  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