Submission #554595

#	Time	Username	Problem	Language	Result	Execution time	Memory
554595		MilosMilutinovic	Food Court (JOI21_foodcourt)	C++14	100 / 100	634 ms	80464 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> t(q);
  vector<int> l(q);
  vector<int> r(q);
  vector<int> c(q);
  vector<long long> k(q);
  vector<long long> a(q);
  vector<long long> b(q);
  vector<vector<pair<int, long long>>> qs(n + 1);
  vector<vector<pair<int, long long>>> xs(n + 1);
  vector<vector<pair<int, long long>>> fs(n + 1);
  for (int i = 0; i < q; i++) {
    cin >> t[i];
    if (t[i] == 1) {
      cin >> l[i] >> r[i] >> c[i] >> k[i];
      --l[i];
      qs[l[i]].emplace_back(i, k[i]);
      qs[r[i]].emplace_back(i, 0);
      fs[l[i]].emplace_back(i, k[i]);
      fs[r[i]].emplace_back(i, 0);
    } else if (t[i] == 2) {
      cin >> l[i] >> r[i] >> k[i];
      --l[i];
      qs[l[i]].emplace_back(i, -k[i]);
      qs[r[i]].emplace_back(i, 0);
    } else {
      cin >> a[i] >> b[i];
      --a[i];
      xs[a[i]].emplace_back(i, b[i]);
    }
  }
  vector<long long> sum(4 * q);
  vector<long long> suf(4 * q);
  vector<long long> st(4 * q);  
  function<void(int, int, int, int, long long)> modify = [&](int node, int l, int r, int i, long long v) {
    if (l == r) {
      sum[node] = v;
      suf[node] = max(0LL, v);
      return;
    }
    int mid = l + r >> 1;
    if (i <= mid) {
      modify(node + node, l, mid, i, v);
    } else {
      modify(node + node + 1, mid + 1, r, i, v);
    }
    sum[node] = sum[node + node] + sum[node + node + 1]; 
    suf[node] = max(suf[node + node + 1], suf[node + node] + sum[node + node + 1]);
  };
  function<pair<long long, long long>(int, int, int, int, int)> query = [&](int node, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll) return make_pair(0LL, 0LL);
    if (ll <= l && r <= rr) return make_pair(sum[node], suf[node]);
    int mid = l + r >> 1;
    auto L = query(node + node, l, mid, ll, rr);
    auto R = query(node + node + 1, mid + 1, r, ll, rr);
    return make_pair(L.first + R.first, max(R.second, L.second + R.first));
  };
  function<void(int, int, int, int, long long)> update = [&](int node, int l, int r, int i, long long x) {    
    if (l == r) {
      st[node] = x;
      return;
    }
    int mid = l + r >> 1;
    if (i <= mid) {
      update(node + node, l, mid, i, x);
    } else {
      update(node + node + 1, mid + 1, r, i, x);
    }
    st[node] = st[node + node] + st[node + node + 1];
  };
  function<long long(int, int, int, int, int)> get = [&](int node, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll) return 0LL;
    if (ll <= l && r <= rr) return st[node];
    int mid = l + r >> 1;
    return get(node + node, l, mid, ll, rr) + get(node + node + 1, mid + 1, r, ll, rr);
  };
  function<int(int, int, int, long long)> walk = [&](int node, int l, int r, long long x) {
    if (l == r) {
      return st[node] > x ? l - 1 : l;
    }
    int mid = l + r >> 1;
    if (st[node + node] > x) {
      return walk(node + node, l, mid, x);
    } else {
      return walk(node + node + 1, mid + 1, r, x - st[node + node]);
    }
  };
  vector<long long> ans(q);
  for (int i = 0; i < n; i++) {
    for (auto& p : qs[i]) {
      modify(1, 0, q - 1, p.first, p.second);
    }
    for (auto& p : fs[i]) {
      update(1, 0, q - 1, p.first, p.second);
    }
    for (auto& p : xs[i]) {
      long long curr = query(1, 0, q - 1, 0, p.first).second;
      if (curr < p.second) {
        ans[p.first] = 0;      
      } else {             
        long long d = get(1, 0, q - 1, 0, p.first) - curr + p.second;
        ans[p.first] = c[walk(1, 0, q - 1, d - 1) + 1];
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (t[i] == 3) {
      cout << ans[i] << '\n';
    }
  }                        
  return 0;
}

Compilation message (stderr)

foodcourt.cpp: In lambda function:
foodcourt.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In lambda function:
foodcourt.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In lambda function:
foodcourt.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In lambda function:
foodcourt.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: In lambda function:
foodcourt.cpp:89:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int mid = l + r >> 1;
      |               ~~^~~

• 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