oj.uz

Submission #769922

# Submission time Handle Problem Language Result Execution time Memory
769922 2023-06-30T13:47:16 Z EdneyVF Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1047 ms 112832 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 22 ms 47188 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 80188 KB Output is correct
2 Correct 57 ms 80128 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 80084 KB Output is correct
2 Correct 61 ms 80192 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 63956 KB Output is correct
2 Correct 77 ms 63944 KB Output is correct
3 Correct 78 ms 64056 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 64852 KB Output is correct
2 Correct 255 ms 64968 KB Output is correct
3 Correct 203 ms 64860 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 65512 KB Output is correct
2 Correct 61 ms 65356 KB Output is correct
3 Correct 329 ms 64932 KB Output is correct
4 Correct 412 ms 65564 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 66076 KB Output is correct
2 Correct 725 ms 65740 KB Output is correct
3 Correct 364 ms 66144 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 66420 KB Output is correct
2 Correct 963 ms 66304 KB Output is correct
3 Correct 941 ms 66268 KB Output is correct
4 Correct 1004 ms 66280 KB Output is correct
5 Correct 1047 ms 66244 KB Output is correct
6 Correct 468 ms 66488 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 97208 KB Output is correct
2 Correct 272 ms 62824 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 105224 KB Output is correct
2 Correct 636 ms 102008 KB Output is correct
3 Correct 372 ms 96448 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 112832 KB Output is correct
2 Correct 952 ms 110664 KB Output is correct
3 Correct 942 ms 110500 KB Output is correct
4 Correct 836 ms 108932 KB Output is correct
5 Correct 555 ms 103884 KB Output is correct