Submission #1274754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274754		zNatsumi	푸드 코트 (JOI21_foodcourt)	C++20	13 / 100	283 ms	39172 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;

const int N = 3e5 + 5;

int n, m, q, c[N], res[N];
vector<int> cl[N];
vector<pair<int, int>> op[N];
vector<pair<int, i64>> que[N];

i64 f[N << 2], g[N << 2], t[N << 2]; // sum, sum of non-negative, minimum prefix

void update(int x, int y, int tl = 1, int tr = q, int i = 1){
  if(tl == tr){
    f[i] = t[i] = y;
    if(x >= 0) g[i] = y;
    return;
  }
  int tm = tl + tr >> 1;
  if(x <= tm) update(x, y, tl, tm, i<<1);
  else update(x, y, tm + 1, tr, i<<1|1);

  f[i] = f[i<<1] + f[i<<1|1];
  g[i] = g[i<<1] + g[i<<1|1];
  t[i] = min(t[i<<1], f[i<<1] + t[i<<1|1]);
}

i64 sum = 0;
void CountCustomer(int l, int r, int tl = 1, int tr = q, int i = 1){
  if(r < tl || tr < l || l > r) return;
  if(l <= tl && tr <= r){
    if(sum + t[i] <= 0) sum = f[i] - t[i];
    else sum += f[i];
    return;
  }
  int tm = tl + tr >> 1;
  CountCustomer(l, r, tl, tm, i<<1);
  CountCustomer(l, r, tm + 1, tr, i<<1|1);
}

int pos;
void Query(int l, int r, int tl = 1, int tr = q, int i = 1){
  if(r < tl || tr < l || l > r) return;
  if(l <= tl && tr <= r){
    if(tl == tr && g[i] >= sum){
      pos = tl;
      return;
    }
    int tm = tl + tr >> 1;
    if(sum > g[i]) sum -= g[i];
    else if(sum > g[i<<1|1]){
      sum -= g[i<<1|1];
      Query(l, r, tl, tm, i<<1);
    }else Query(l, r, tm + 1, tr, i<<1|1);

    return;
  }
  int tm = tl + tr >> 1;
  if(pos == -1) Query(l, r, tm + 1, tr, i<<1|1);
  if(pos == -1) Query(l, r, tl, tm, i<<1);
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m >> q;
  for(int i = 1; i <= q; i++){
    int type; cin >> type;
    if(type == 1){
      int l, r, k; cin >> l >> r >> c[i] >> k;
      op[l].push_back({i, k});
      cl[r + 1].push_back(i);
    }
    if(type == 2){
      int l, r, k; cin >> l >> r >> k;
      op[l].push_back({i, -k});
      cl[r + 1].push_back(i);
    }
    if(type == 3){
      int a; cin >> a;
      i64 b; cin >> b;
      que[a].push_back({i, b});
    }
    res[i] = -1;
  }

  for(int i = 1; i <= n; i++){
    for(auto [idx, val] : op[i]) update(idx, val);
    for(auto idx : cl[i]) update(idx, 0);

    for(auto [idx, b] : que[i]){
      sum = 0;
      CountCustomer(1, idx);

      if(sum < b){
        res[idx] = 0;
        continue;
      }
      sum = sum - b + 1;
      pos = -1; Query(1, idx);
      res[idx] = c[pos];
    }
  }
  for(int i = 1; i <= q; i++) if(res[i] != -1) cout << res[i] << "\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: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11