제출 #1255498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255498		LucaLucaM	푸드 코트 (JOI21_foodcourt)	C++20	2 / 100	1093 ms	9284 KiB

foodcourt

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

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

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

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

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

  std::vector<Query> Q(q);
  for (auto &[type, l, r, c, k] : Q) {
    std::cin >> type;
    if (type == 1) {
      std::cin >> l >> r >> c >> k;
    } else if (type == 2) {
      std::cin >> l >> r >> k;
    } else {
      std::cin >> l >> r;
    }
  }

  Q.insert(Q.begin(), Query{});
  
  auto query1 = [&](int p, int t) {
    int ret = 0;
    for (int i = 1; i <= t; i++) {
      if (Q[i].l <= p && p <= Q[i].r) {
        if (Q[i].type == 1) {
          ret += Q[i].k;
        } else if (Q[i].type == 2) {
          ret = std::max(0, ret - Q[i].k);
        }
      }
    }
    return ret;
  };

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

  for (int i = 1; i <= q; i++) {
    if (Q[i].type == 3) {
      int A = Q[i].l, B = Q[i].r;
      if (query1(A, i) < B) {
        std::cout << "0\n";
        continue;
      }
      int l = 0, r = i - 1;
      // for (int j = 1; j <= i; j++) {
      //   std::cout << query1(A, j) + query2(A, j + 1, i) << ' ';
      // }
      // std::cout << '\n';
      while (l < r) {
        int mid = (l + r) / 2;
        if (query1(A, mid) + query2(A, mid + 1, i) >= B) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      // std::cout << "\n\n ! ";
      // std::cout << query1(1, 2) << ' ';
      // std::cout << query2(1, 3, 5) << ' ';
      std::cout << Q[r].c << '\n';
    }
  }
  
  return 0;
}

• Subtask 1: 2 / 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