Submission #794182

#	Time	Username	Problem	Language	Result	Execution time	Memory
794182		rxlfd314	Pyramid Base (IOI08_pyramid_base)	C++17	70 / 100	5062 ms	118516 KiB

pyramid_base

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

struct Segtree {
	vector<int> ladd, sgt;
	Segtree(int N) {
		ladd.resize(N<<2, 0);
		sgt.resize(N<<2, 0);
	}
	void push(int i) {
		if (!ladd[i]) return;
		ladd[i<<1] += ladd[i];
		ladd[i<<1|1] += ladd[i];
		sgt[i<<1] += ladd[i];
		sgt[i<<1|1] += ladd[i];
		ladd[i] = 0;
	}
	void radd(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
		if (tr < 0) tr += sgt.size() >> 2;
		if (tl > qr || tr < ql) return;
		if (ql <= tl && tr <= qr) {
			sgt[i] += v, ladd[i] += v;
		} else {
			push(i);
			int mid = tl + tr >> 1;
			radd(ql, qr, v, i<<1, tl, mid);
			radd(ql, qr, v, i<<1|1, mid+1, tr);
			sgt[i] = min(sgt[i<<1], sgt[i<<1|1]);
		}
	}
	int qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
		if (tr < 0) tr += sgt.size() >> 2;
		if (tl > qr || tr < ql) return INT_MAX;
		if (ql <= tl && tr <= qr) return sgt[i];
		push(i);
		int mid = tl + tr >> 1;
		return min(qry(ql, qr, i<<1, tl, mid), qry(ql, qr, i<<1|1, mid+1, tr));
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, M, B, P;
	cin >> N >> M >> B >> P;
	vector<vector<int>> A(P, vector<int>(5));
	for (auto &v : A) {
		for (int &i : v) {
			cin >> i, i--;
		}
		v[4]++;
	}
	if (1) {
		int lo = 0, hi = min(N, M);
		while (lo < hi) {
			int mid = lo + hi + 1 >> 1;
			vector<vector<int>> evs;
			for (auto &v : A) {
				evs.push_back({v[0], max(0, v[1]-mid+1), min(M-mid, v[3]), v[4]});
				if (v[2] + mid < N) {
					evs.push_back({v[2] + mid, max(0, v[1]-mid+1), min(M-mid, v[3]), -v[4]});
				}
			}
			sort(evs.begin(), evs.end());
			Segtree sgt(M-mid+1);
			bool can = false;
			for (int i = mid-1, j = 0; i < N; i++) {
				for (; j < evs.size() && evs[j][0] <= i; j++) {
					sgt.radd(evs[j][1], evs[j][2], evs[j][3]);
				}
				can |= sgt.qry(0, M-mid) <= B;
			}
			can ? lo = mid : hi = mid - 1;
		}
		cout << lo << '\n';
	}
}

Compilation message (stderr)

pyramid_base.cpp: In member function 'void Segtree::radd(int, int, int, int, int, int)':
pyramid_base.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |    int mid = tl + tr >> 1;
      |              ~~~^~~~
pyramid_base.cpp: In member function 'int Segtree::qry(int, int, int, int, int)':
pyramid_base.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = tl + tr >> 1;
      |             ~~~^~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |    int mid = lo + hi + 1 >> 1;
      |              ~~~~~~~~^~~
pyramid_base.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (; j < evs.size() && evs[j][0] <= i; j++) {
      |            ~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10