Submission #580596

#	Time	Username	Problem	Language	Result	Execution time	Memory
580596		pure_mem	Pyramid Base (IOI08_pyramid_base)	C++14	70 / 100	5036 ms	62040 KiB

pyramid_base

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 4e5 + 19, M = 2e6;
const ll INF = 1e9 + 7, MAX = 1e18, mod = 1e9 + 7;

int t[N * 4], tt[N * 4];

void push(int v) {
	if(!tt[v])
		return;
	
	t[v * 2] += tt[v];
	t[v * 2 + 1] += tt[v];
	 
	tt[v * 2] += tt[v];
	tt[v * 2 + 1] += tt[v];
	
	tt[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int val) {
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r) {
		tt[v] += val;
		t[v] += val;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v] = min(t[v * 2], t[v * 2 + 1]);
}

int n, m, B, q;
array<int, 5> qq[N];
vector<int> px(1, 1), py(1, 1);

bool check(int len) {
	int lm = 1;
	while(lm < (int)py.size() && py[lm] + len - 1 <= n)
		lm++;
	vector< array<int, 4> > all;

	for(int i = 1;i <= lm * 4;i++)
		t[i] = tt[i] = 0;

	for(int i = 1;i <= q;i++) {
		all.push_back({qq[i][0] - len + 1, qq[i][2] - len + 1, qq[i][3], qq[i][4]});	
		all.push_back({qq[i][1] + 1, qq[i][2] - len + 1, qq[i][3], -qq[i][4]});	
	}

	sort(all.begin(), all.end());

	int it = 0, ok = 0;
	for(int x: px) {
		while(it < (int)all.size() && all[it][0] <= x) {
			int l = all[it][1], r = all[it][2];
			l = lower_bound(py.begin(), py.end(), l) - py.begin() + 1;
			r = upper_bound(py.begin(), py.end(), r) - py.begin();
			r = min(r, lm);
			
			if(l <= lm)
				upd(1, 1, lm, l, r, all[it][3]);
			it++;
		}
		if(x + len - 1 <= m && !ok && t[1] <= B)
			ok = 1;
	}
	return ok;
}

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n;
    cin >> B;

  	cin >> q;
    for(int i = 1;i <= q;i++) {
    	int x1, y1, x2, y2, c;
    	cin >> x1 >> y1 >> x2 >> y2 >> c;
    	qq[i] = {x1, x2, y1, y2, c};
    	if(x2 + 1 <= m)
    		px.push_back(x2 + 1);
    	if(y2 + 1 <= n)
    		py.push_back(y2 + 1);
    }

    sort(px.begin(), px.end()); 
    px.erase(unique(px.begin(), px.end()), px.end());
    sort(py.begin(), py.end()); 
    py.erase(unique(py.begin(), py.end()), py.end());


	int l = 1, r = min(n, m);
	while(l <= r) {
		int mid = (l + r) / 2;
		if(check(mid)) {
			l = mid + 1;
		}		
		else {
			r = mid - 1;
		}
	}

	cout << l - 1;
}

• 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