oj.uz

Submission #580596

# Submission time Handle Problem Language Result Execution time Memory
580596 2022-06-21T13:32:28 Z pure_mem Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 62040 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 348 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 468 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Output is correct
2 Correct 14 ms 468 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 520 KB Output is correct
2 Correct 11 ms 480 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1092 KB Output is correct
2 Correct 84 ms 1144 KB Output is correct
3 Correct 75 ms 1104 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 2524 KB Output is correct
2 Correct 383 ms 2608 KB Output is correct
3 Correct 287 ms 2484 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 3524 KB Output is correct
2 Correct 74 ms 2952 KB Output is correct
3 Correct 225 ms 3644 KB Output is correct
4 Correct 510 ms 3788 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 4188 KB Output is correct
2 Correct 635 ms 4204 KB Output is correct
3 Correct 314 ms 3888 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 4484 KB Output is correct
2 Correct 827 ms 4908 KB Output is correct
3 Correct 834 ms 4820 KB Output is correct
4 Correct 871 ms 4840 KB Output is correct
5 Correct 813 ms 4808 KB Output is correct
6 Correct 336 ms 4344 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 31900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5006 ms 51304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 62040 KB Time limit exceeded
2 Halted 0 ms 0 KB -