Submission #386363

#	Time	Username	Problem	Language	Result	Execution time	Memory
386363		Mamnoon_Siam	Food Court (JOI21_foodcourt)	C++17	100 / 100	686 ms	63380 KiB

foodcourt

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

struct info {
  ll x = 0, y = 0;
  info operator + (const info& o) const {
    info r;
    if(y >= o.x) r.y = y - o.x, r.x = x;
    else r.y = 0, r.x = x + (o.x - y);
    r.y += o.y;
    return r;
  }
};

struct Node {
  Node *l = 0, *r = 0;
  info lz;
  int lo, hi;
  Node(int _lo, int _hi) : lo(_lo), hi(_hi) {
    if(lo < hi) {
      int mid = (lo + hi) >> 1;
      l = new Node(lo, mid), r = new Node(mid+1, hi);
    }
  }
  void update(int L, int R, info v) {
    if(lo > R or hi < L) return;
    if(L <= lo and hi <= R) {
      lz = lz + v;
    } else {
      push();
      l -> update(L, R, v);
      r -> update(L, R, v);
    }
  }
  ll query(int pos) {
    if(lo == hi) return lz.y;
    else {
      push();
      return pos <= l -> hi ? l -> query(pos) : r -> query(pos);
    }
  }
  void push() {
    if(lo < hi) {
      l -> lz = l -> lz + lz;
      r -> lz = r -> lz + lz;
    }
    lz = info();
  }
};

const int N = 250005;
const int lg = 19;

int n, m, q;
int type[N], L[N], R[N], A[N], C[N], K[N];
int lo[N], hi[N], mid[N];
ll B[N];
vi upds[N], ask[N];
int ans[N];

namespace bit {
  ll ft[N];
  void update(int p, ll x) {
    for(; p <= q; p += p & -p) ft[p] += x;
  }
  int query(ll x) { // minimum i such that sum(1, i) <= x
    int idx = 0;
    ll sm = 0;
    for(int pw = 1 << (lg-1); pw; pw >>= 1) {
      if((idx|pw) <= q and sm + ft[idx|pw] < x) {
        idx |= pw;
        sm += ft[idx];
      }
    }
    return idx+1;
  }
}
namespace bit2 {
  ll ft[N];
  void update(int l, int r, ll x) {
    for(; l <= n; l += l & -l) ft[l] += x;
    for(++r; r <= n; r += r & -r) ft[r] -= x;
  }
  ll query(int p, ll ret = 0) {
    for(; p > 0; p -= p & -p) ret += ft[p];
    return ret;
  }
}

Node* tr;

void Join(int l, int r, int c, int k) {
  tr -> update(l, r, info{0, k});
  bit2::update(l, r, k);
}

void Leave(int l, int r, int k) {
  tr -> update(l, r, info{k, 0});
}

ll Service(int a, ll b) {
  ll tmp = tr -> query(a);
  return tmp < b ? ll(1e15) : b + bit2::query(a) - tmp;
  // return tr -> query(a) >= b;
}

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d %d", &n, &m, &q);
  // assert(m == 1);
  tr = new Node(1, n);
  for(int i = 1; i <= q; ++i) {
    int &t = type[i]; scanf("%d", &t);
    if(t == 1) {
      int &l = L[i], &r = R[i], &c = C[i], &k = K[i];
      scanf("%d %d %d %d", &l, &r, &c, &k);
      Join(l, r, c, k);
      upds[l].emplace_back(i);
      upds[r+1].emplace_back(-i);
    } else if(t == 2) {
      int &l = L[i], &r = R[i], &k = K[i];
      scanf("%d %d %d", &l, &r, &k);
      Leave(l, r, k);
    } else {
      int &a = A[i]; ll &b = B[i];
      scanf("%d %lld", &a, &b);
      b = Service(a, b);
      ask[a].emplace_back(i);
      // printf("%d\n", Service(a, b));
    }
  }

  for(int i = 1; i <= n; ++i) {
    for(int j : upds[i]) {
      if(j > 0) bit::update(j, K[j]);
      else bit::update(-j, -K[-j]);
    }
    for(int j : ask[i]) {
      ans[j] = bit::query(B[j]);
    }
  }

  for(int i = 1; i <= q; ++i) if(type[i] == 3) {
    printf("%d\n", ans[i] > q ? 0 : C[ans[i]]);
  }
  return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main(int, const char**)':
foodcourt.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |   scanf("%d %d %d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:124:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |     int &t = type[i]; scanf("%d", &t);
      |                       ~~~~~^~~~~~~~~~
foodcourt.cpp:127:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |       scanf("%d %d %d %d", &l, &r, &c, &k);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:133:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |       scanf("%d %d %d", &l, &r, &k);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:137:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |       scanf("%d %lld", &a, &b);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~

• 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