oj.uz

Submission #119120

# Submission time Handle Problem Language Result Execution time Memory
119120 2019-06-20T11:49:09 Z tmwilliamlin168 Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 85256 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxP=4e5, mxM=1e6;
int m, n, b, p, ans, st[1<<21], lz[1<<21];
vector<array<int, 3>> r1[mxM], r2[mxM+1];

void app(int i, int x) {
	st[i]+=x;
	lz[i]+=x;
}

void psh(int i) {
	app(2*i, lz[i]);
	app(2*i+1, lz[i]);
	lz[i]=0;
}

void upd(int l1, int r1, int x, int i=1, int l2=0, int r2=n-1) {
	if(l1<=l2&&r2<=r1) {
		app(i, x);
		return;
	}
	int m2=(l2+r2)/2;
	psh(i);
	if(l1<=m2)
		upd(l1, r1, x, 2*i, l2, m2);
	if(m2<r1)
		upd(l1, r1, x, 2*i+1, m2+1, r2);
	st[i]=min(st[2*i], st[2*i+1]);
}

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

	cin >> m >> n >> b >> p;
	for(int i=0, xa, ya, xb, yb, c; i<p; ++i) {
		cin >> xa >> ya >> xb >> yb >> c, --xa, --ya, --xb, --yb;
		r1[xa].push_back({ya, yb, c});
		r2[xb+1].push_back({ya, yb, c});
	}
	if(1) {
		int lb=0, rb=n;
		while(lb<rb) {
			int mb=(lb+rb+1)/2;
			bool ok=0;
			memset(st, 0, sizeof(st));
			memset(lz, 0, sizeof(lz));
			if(mb>1)
				upd(n-mb+1, n-1, 3e8);
			for(int i=0; i<mb-1; ++i)
				for(array<int, 3> a : r1[i])
					upd(a[0]-mb+1, a[1], a[2]);
			for(int i=0; i<=m-mb&&!ok; ++i) {
				for(array<int, 3> a : r1[i+mb-1])
					upd(a[0]-mb+1, a[1], a[2]);
				for(array<int, 3> a : r2[i])
					upd(a[0]-mb+1, a[1], -a[2]);
				ok=st[1]<=b;
			}
			if(ok)
				lb=mb;
			else
				rb=mb-1;
		}
		ans=lb;
	} else {
		;
	}
	cout << ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 63828 KB Output is correct
2 Correct 305 ms 63828 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 63736 KB Output is correct
2 Correct 223 ms 63816 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 64084 KB Output is correct
2 Correct 123 ms 64144 KB Output is correct
3 Correct 121 ms 63992 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 64636 KB Output is correct
2 Correct 391 ms 65144 KB Output is correct
3 Correct 349 ms 64908 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 65020 KB Output is correct
2 Correct 107 ms 65528 KB Output is correct
3 Correct 450 ms 64828 KB Output is correct
4 Correct 616 ms 65528 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 65272 KB Output is correct
2 Correct 1026 ms 65912 KB Output is correct
3 Correct 550 ms 66120 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 65656 KB Output is correct
2 Correct 1403 ms 66296 KB Output is correct
3 Correct 1326 ms 66332 KB Output is correct
4 Correct 1501 ms 66320 KB Output is correct
5 Correct 1446 ms 66268 KB Output is correct
6 Correct 631 ms 66424 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5046 ms 75272 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 5025 ms 80456 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 5027 ms 85256 KB Time limit exceeded
2 Halted 0 ms 0 KB -