oj.uz

Submission #119143

# Submission time Handle Problem Language Result Execution time Memory
119143 2019-06-20T13:25:39 Z tmwilliamlin168 Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 1480 ms 108856 KB 
#include <bits/stdc++.h>
using namespace std;

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

namespace subtask2 {
	int st[1<<21], lz[1<<21];

	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]);
	}

	void solve() {
		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;
	}
}

namespace subtask3 {
	array<int, 4> st[1<<21];

	void cmb(int i, int l, int m, int r) {
		int lt=st[2*i][1], ll=st[2*i][2], lr=st[2*i][3], rt=st[2*i+1][1], rl=st[2*i+1][2], rr=st[2*i+1][3];
		if(st[2*i][0])
			lt=ll=lr=0;
		if(st[2*i+1][0])
			rt=rl=rr=0;
		st[i]={st[i][0], max({lt, rt, lr+rl}), ll+(ll<m-l+1?0:rl), rr+(rr<r-m?0:lr)};
	}

	void bld(int i=1, int l=0, int r=n-1) {
		if(l==r) {
			st[i]={0, 1, 1, 1};
			return;
		}
		int m=(l+r)/2;
		bld(2*i, l, m);
		bld(2*i+1, m+1, r);
		cmb(i, l, m, r);
	}

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

	void solve() {
		r1[m].push_back({0, n-1});
		bld();
		for(int i1=0, i2=0; i1<m; ++i1) {
			for(array<int, 3> a : r2[i1])
				upd(a[0], a[1], -1);
			for(; (st[1][0]?0:st[1][1])>=i2-i1; ++i2) {
				ans=max(i2-i1, ans);
				for(array<int, 3> a : r1[i2])
					upd(a[0], a[1], 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(b)
		subtask2::solve();
	else
		subtask3::solve();
	cout << ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 80128 KB Output is correct
2 Correct 87 ms 80248 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 80204 KB Output is correct
2 Correct 87 ms 80220 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 64136 KB Output is correct
2 Correct 137 ms 64124 KB Output is correct
3 Correct 135 ms 64108 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 64888 KB Output is correct
2 Correct 405 ms 65040 KB Output is correct
3 Correct 348 ms 64888 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 65560 KB Output is correct
2 Correct 112 ms 65400 KB Output is correct
3 Correct 542 ms 65004 KB Output is correct
4 Correct 659 ms 65528 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 66012 KB Output is correct
2 Correct 1125 ms 66040 KB Output is correct
3 Correct 589 ms 66040 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 66380 KB Output is correct
2 Correct 1480 ms 66168 KB Output is correct
3 Correct 1382 ms 66296 KB Output is correct
4 Correct 1394 ms 66040 KB Output is correct
5 Correct 1439 ms 66168 KB Output is correct
6 Correct 654 ms 66296 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 92360 KB Output is correct
2 Correct 396 ms 62888 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 97944 KB Output is correct
2 Correct 921 ms 102204 KB Output is correct
3 Correct 566 ms 96640 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1115 ms 102584 KB Output is correct
2 Correct 1295 ms 108856 KB Output is correct
3 Correct 1286 ms 108780 KB Output is correct
4 Correct 1175 ms 107356 KB Output is correct
5 Correct 769 ms 101940 KB Output is correct