Submission #548661

#	Time	Username	Problem	Language	Result	Execution time	Memory
548661		quocnguyen1012	Food Court (JOI21_foodcourt)	C++14	100 / 100	414 ms	56964 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;
  }
  int kth(T val) {
    int pos = 0;
    for (int i = 17; i >= 0; --i) {
      if (pos + (1 << i) < (int)bit.size() and bit[pos + (1 << i)] < val) {
        pos += (1 << i);
        val -= bit[pos];
      }
    }
    return pos + 1;
  }
};

struct Tree {
  struct node {
    int64_t sufmax, sum;
    node(int64_t sufmax = 0, int64_t sum = 0):
      sufmax(sufmax), sum(sum) {}
    node operator + (const node &oth) const {
      return node(max(oth.sufmax, sufmax + oth.sum),
                  sum + oth.sum);
    }
  };
	vector<node> s; int n;
	Tree(int n = 0) : s(2*n), n(n) {}
	void update(int pos, int64_t val) {
		for (s[pos += n] = node(max((int64_t)0, val), val); pos /= 2;)
			s[pos] = s[pos * 2] + s[pos * 2 + 1];
	}
	node fquery(int b, int e) { // query [b, e)
		node ra, rb;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = ra + s[b++];
			if (e % 2) rb = s[--e] + rb;
		}
		return ra + rb;
	}
  node query(int b, int e) {return fquery(b, e + 1); }
};


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(Q + 5);
  Tree seg(Q + 5);
  vector<vector<pair<int64_t, int64_t>>> queries(N + 5), fwupd(N + 5), upd(N + 5);
  vector<int> group(Q + 5), res(Q + 5, -1);
  for (int i = 1; i <= Q; ++i) {
    int64_t op, a, b, c, k;
    cin >> op;
    if (op == 1) {
      cin >> a >> b >> c >> k;
      group[i] = c;
      upd[a].emplace_back(i, k);
      upd[b + 1].emplace_back(i, 0);
      fwupd[a].emplace_back(i, k);
      fwupd[b + 1].emplace_back(i, -k);
    } else if (op == 2) {
      cin >> a >> b >> k;
      upd[a].emplace_back(i, -k);
      upd[b + 1].emplace_back(i, 0);
    } else {
      cin >> a >> b;
      queries[a].emplace_back(i, b);
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (auto &[pos, val] : upd[i]) {
      seg.update(pos, val);
    }
    for (auto &[pos, val] : fwupd[i]) {
      tot.add(pos, val);
    }
    for (auto &[pos, val] : queries[i]) {
      auto cur = seg.query(1, pos);
      if (cur.sufmax >= val) {
        int64_t kth = tot.query(pos) - (cur.sufmax - val);
        res[pos] = group[tot.kth(kth)];
      } else {
        res[pos] = 0;
      }
    }
  }
  for (int i = 1; i <= Q; ++i) if (res[i] != -1) cout << res[i] << '\n';
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:88:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for (auto &[pos, val] : upd[i]) {
      |                ^
foodcourt.cpp:91:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |     for (auto &[pos, val] : fwupd[i]) {
      |                ^
foodcourt.cpp:94:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for (auto &[pos, val] : queries[i]) {
      |                ^

• 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