Submission #1127861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127861		VinhLuu	Food Court (JOI21_foodcourt)	C++20	24 / 100	351 ms	49008 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;

#define lpv

#ifndef lpv
#include "AC.h"
#endif // lpv

//#define int long long

const int N = 3e5 + 5;

int n, m, q, type[N], L[N], C[N], K[N], sz[N], kq[N];
ll R[N];

vector<int> Q[N];

ll st[N << 2], T[N << 2], f[N << 2];

void change(int i,int l,int r,int u,int x) {
  if(l > r || r < u || u < l) return;
  if(l == r) {
    st[i] = x;
    T[i] = x;
    if(x >= 0) f[i] = x;
    return;
  }
  int mid = (l + r) / 2;
  change(i << 1, l, mid, u, x);
  change(i << 1|1, mid + 1, r, u, x);
  st[i] = st[i << 1] + st[i << 1|1];
  T[i] = min(T[i << 1], st[i << 1] + T[i << 1|1]);
  f[i] = f[i << 1] + f[i << 1|1];
//  cerr << i << " " << l << " " << r << " " << st[i] << " " << T[i] << " " << f[i] << "k\n";
}

ll sum = 0;

void query(int i,int l,int r,int u,int v) {
  if(l > r || r < u || v < l) return;
  if(u <= l && r <= v) {
    if(sum + T[i] <= 0) sum = st[i] - T[i];
    else sum += st[i];
    return;
  }
  int mid = (l + r) / 2;
  query(i << 1, l, mid, u, v);
  query(i << 1|1, mid + 1, r, u, v);
}

bool flag;
int re, pos;

void get(int i,int l,int r,int u,int v) {
  if(l > r || r < u || v < l) return;
  if(u <= l && r <= v) {
    if(f[i] < re) {
      re -= f[i];
      return;
    }
    flag = 0;
//    cerr << i << " " << l << " " << r << " " << f[i] << " " << f[i << 1] << " " << f[i << 1|1] << " k\n";
    if(l == r) {
      pos = l;
    } else {
      int mid = (l + r) / 2;
      if(f[i << 1|1] < re) {
        re -= f[i << 1|1];
        get(i << 1, l, mid, u, v);
      } else {

        get(i << 1|1, mid + 1, r, u, v);
      }
    }
    return;
  }
  int mid = (l + r) / 2;
  if(flag) get(i << 1|1, mid + 1, r, u, v);
  if(flag) get(i << 1, l, mid, u, v);

}

vector<pair<int,int>> op[N], cl[N];


#ifdef lpv
signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  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 ++) {
    cin >> type[i];
    if(type[i] == 1) cin >> L[i] >> R[i] >> C[i] >> K[i];
    else if(type[i] == 2) cin >> L[i] >> R[i] >> K[i];
    else cin >> L[i] >> R[i];
  }

  for(int i = 1; i <= q; i ++) {
    if(type[i] == 3) Q[L[i]].push_back(i);
    else if (type[i] == 1) {
      op[L[i]].push_back({1, i});
      cl[R[i] + 1].push_back({1, i});
    } else if (type[i] == 2) {
      op[L[i]].push_back({0, i});
      cl[R[i] + 1].push_back({0, i});
    }
  }

  for(int i = 1; i <= n; i ++) {
//    cerr << i << " start\n";

    for(auto [t, id] : op[i]) {
      if(t) change(1, 1, q, id, K[id]);
      else change(1, 1, q, id, -K[id]);
    }
    for(auto [t, id] : cl[i]) {
      change(1, 1, q, id, 0);
    }
    for(auto id : Q[i]) {
      sum = 0;
      query(1, 1, q, 1, id);
//      cerr << id << " " << sum << " " << R[id] << " f\n";
      if(sum < R[id]) {
        kq[id] = 0;
        continue;
      } else {
        pos = 0;
        re = sum - R[id] + 1;
        flag = 1;
//        cerr << re << " " << q << " " << id << " t\n";
        get(1, 1, q, 1, id);
        kq[id] = C[pos];
      }
    }
  }
  for(int i = 1; i <= q; i ++) if(type[i] == 3) cout << kq[i] << "\n";

}
#endif // lpv

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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