Submission #548030

#	Time	Username	Problem	Language	Result	Execution time	Memory
548030		quocnguyen1012	푸드 코트 (JOI21_foodcourt)	C++14	0 / 100	440 ms	52052 KiB

foodcourt

#include "bits/stdc++.h"

using namespace std;

template<class T>struct fenwick {
  vector<T> bit;
  fenwick(int n) {
    bit.assign(n + 5, 0);
  } 
  void add(int i, T delta) {
    for (; i < (int)bit.size(); i += i & -i)
      bit[i] += delta;
  }
  T query(int i) {
    T ans = 0;
    for (; i; i -= i & -i) {
      ans += bit[i];
    }
    return ans;
  }
};

template<class T>class lazy_segtree {
private:
  vector<T> st, lz;
  int n;
#define lc id << 1
#define rc id << 1 | 1
  void push(int id, int l, int r) {
    st[id] += lz[id];
    if (l != r) {
      lz[lc] += lz[id];
      lz[rc] += lz[id];    
    }
    lz[id] = 0;
  }
  void modify(int L, int R, T val, int id, int l, int r) {
    if (R < l || r < L) return;
    push(id, l, r);
    if (L <= l && r <= R) {
      lz[id] += val;
      push(id, l, r);
      return;
    }
    int mid = (l + r) / 2;
    modify(L, R, val, lc, l, mid);
    modify(L, R, val, rc, mid + 1, r);
    st[id] = min(st[lc], st[rc]);
  }
  T getmin(int id, int l, int r, int L, int R)
  {
    push(id, l, r);
    if (l > R || L > r) return LLONG_MAX;
    if (L <= l && r <= R) return st[id];
    int mid = (l + r) / 2;
    return min(getmin(lc, l, mid, L, R), getmin(rc, mid + 1, r, L, R));
  }
  int findfirst(T value, int id, int l, int r) {
    /// find first position a[x] < value
    push(id, l, r);
    if (st[id] > value) return -1;
    if (l == r) return l;
    int mid = (l + r) / 2;
    push(lc, l, mid); push(rc, mid + 1, r);
    if (st[lc] <= value) return findfirst(value, lc, l, mid);
    else return findfirst(value, rc, mid + 1, r);
  }
public:
  void modify(int L, int R, T val) {
    modify(L, R, val, 1, 1, n);
  }
  T getmin(int L, int R) {
    return getmin(1, 1, n, L, R);
  }
  int findfirst(T val) {
    return findfirst(val, 1, 1, n);
  }
  lazy_segtree(int _n) {
    n = _n;
    st.assign(4 * n + 5, 0);
    lz.assign(4 * n + 5, 0);
  }
};


template<class T>class segtree_beat {
  /// modify: segtree_beat operator
  /// get: query single index
private:
  const int64_t inf = 1e18;
  vector<T> st, lazy;
  int size;
#define lc id << 1
#define rc id << 1 | 1
  void apply(int id, T add, T bound) {
    st[id] = max(bound, st[id] + add);
    lazy[id] += add;
  }
  void push(int id, int ok) {
    if (ok) {
      //cerr << "apply" << ' ' << lazy[id] << ' ' << st[id] << '\n';
      apply(lc, lazy[id], st[id]);
      apply(rc, lazy[id], st[id]);
    }
    lazy[id] = 0;
    st[id] = -inf;
  }
  void modify(int L, int R, T val, int id, int l, int r) {
    if (R < l or r < L) return;
    if (L <= l and r <= R) {
      apply(id, val, -inf);
    } else { 
      push(id, (l != r));
      int mid = (l + r) / 2;
      modify(L, R, val, lc, l, mid);
      modify(L, R, val, rc, mid + 1, r);
    }
  }
  T get(int pos, int id, int l, int r) {
    if (l == r)
      return st[id];
    push(id, (l != r));
  ///  cerr << "debug" << st[lc] << ' ' << st[rc] << ' ' << lazy[id] << '\n';
    int mid = (l + r) / 2;
    if (pos <= mid) return get(pos, lc, l, mid);
    else return get(pos, rc, mid + 1, r);
  }
public:
  segtree_beat(int n) {
    size = n;
    st.resize(4 * size, 0);
    lazy.resize(4 * size, 0);
  }
  void modify(int L, int R, T val) {
    /// a[x] = max(0, a[x] += val);
    modify(L, R, val, 1, 1, size);
    apply(1, 0, 0);
  }
  T get(int pos) {
    return get(pos, 1, 1, size);
  }
  void debug(int id, int l, int r) {
    cerr << l << ' ' << r << ' ' << st[id] << ' ' << lazy[id] << '\n';
    if (l == r) return;
    int mid = (l + r) / 2;
    debug(lc, l, mid); debug(rc, mid + 1, r);
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int N, M, Q; cin >> N >> M >> Q;
  fenwick<int64_t> tot(N + 5);
  segtree_beat<int64_t> cur(N);
  vector<tuple<int, int64_t, int64_t, int64_t, int64_t>> queries(Q);
  vector<vector<pair<int64_t, int>>> ask(N + 5);
  for (int i = 0; i < Q; ++i) {
    auto &[op, a, b, c, k] = queries[i];
    cin >> op;
    if (op == 1) {
      cin >> a >> b >> c >> k;
      tot.add(a, k);tot.add(b + 1, -k);
      cur.modify(a, b, k);
    } else if (op == 2) {
      cin >> a >> b >> k;
      cur.modify(a, b, -k); 
    } else {
      cin >> a >> b;
      int64_t t = tot.query(a);
      int64_t c = cur.get(a);
      if (b <= c) {
        ask[a].emplace_back(t - (c - b), i);
      }
    }
    #ifdef LOCAL
      for (int j = 1; j <= N; ++j) {
        cerr << cur.get(j) << ' ';
      }
      cerr << '\n';
    #endif 
  }
  vector<int> ans(Q), inds(N + 5); 
  lazy_segtree<int64_t> groups(N);
  for (int i = 1; i <= N; ++i) {
    if (ask[i].empty()) {
      groups.modify(i, i, (int64_t)1e17);
    } else {
      sort(ask[i].begin(), ask[i].end());
      groups.modify(i, i, ask[i][0].first);
    }
  }
  for (int i = 0; i < Q; ++i) {
    auto &[op, a, b, c, k] = queries[i];
    if (op == 1) {
      groups.modify(a, b, -k);
      while (true) {
        int pos = groups.findfirst(0);
        if (pos == -1 or pos > N) break;
        ans[ask[pos][inds[pos]].second] = c;
        ++inds[pos];
        if (inds[pos] == ask[pos].size()) groups.modify(pos, pos, (int64_t)1e17);
        else groups.modify(pos, pos, ask[pos][inds[pos]].first - 
                                      ask[pos][inds[pos] - 1].first);
      }
    }
  }
  for (int i = 0; i < Q; ++i) {
    if (get<0>(queries[i]) == 3) cout << ans[i] << '\n';
  }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:158:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |     auto &[op, a, b, c, k] = queries[i];
      |           ^
foodcourt.cpp:193:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  193 |     auto &[op, a, b, c, k] = queries[i];
      |           ^
foodcourt.cpp:201:23: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         if (inds[pos] == ask[pos].size()) groups.modify(pos, pos, (int64_t)1e17);

• 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