oj.uz

Submission #54025

# Submission time Handle Problem Language Result Execution time Memory
54025 2018-07-02T08:33:32 Z 윤교준(#1456) Pyramid Base (IOI08_pyramid_base) C++11
100 / 100
 2198 ms 123548 KB 
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 1000005;
const int MAXM = 1000005;
const int MAXK = 400005;
const int MX = 524288;

struct TC1SEG {
	TC1SEG() { init(); }
	ll d[MAXM*4], e[MAXM*4];
	int M;
	void init() {
		fill(d, d + MAXM * 4, 0);
		fill(e, e + MAXM * 4, 0);
	}
	void upd(int i, int s, int e, int p, int q, int r) {
		if (q < p || e < p || q < s) return;
		if (p <= s && e <= q) {
			TC1SEG::e[i] += r;
			if (s == e) {
				d[i] = TC1SEG::e[i];
			}
			else {
				d[i] = min(d[i * 2], d[i * 2 + 1]) + TC1SEG::e[i];
			}
			return;
		}
		int m = (s + e) / 2;
		upd(i * 2, s, m, p, q, r);
		upd(i * 2 + 1, m + 1, e, p, q, r);
		d[i] = min(d[i * 2], d[i * 2 + 1]) + TC1SEG::e[i];
	}
	void upd(int p, int q, int r) {
		upd(1, 1, M, p, q, r);
	}
	ll get(int i, int s, int e, int p, int q) {
		if (q < p || e < p || q < s) return INFLL;
		if (p <= s && e <= q) return d[i];
		int m = (s + e) / 2;
		return min(get(i * 2, s, m, p, q), get(i * 2 + 1, m + 1, e, p, q)) + TC1SEG::e[i];
	}
	ll get(int s, int e) {
		return get(1, 1, M, s, e);
	}
} tc1seg;

struct EVTTC1 {
	EVTTC1(int type, int x, int a, int b, int c)
		: type(type), x(x), a(a), b(b), c(c) {}
	int type, x, a, b, c;

	bool operator < (const EVTTC1 &t) const {
		if (x != t.x) return x < t.x;
		return type < t.type;
	}
};




struct EVT {
	EVT(int type, int x, int a, int b, int c)
		: type(type), x(x), a(a), b(b), c(c) {}
	int type, x, a, b, c;

	bool operator < (const EVT &t) const {
		if (x != t.x) return x < t.x;
		return type < t.type;
	}
};

struct SEG {
	int dc[MAXN * 4], dl[MAXN * 4], dr[MAXN * 4], dd[MAXN * 4];
	int M;
	
	void init(int i, int s, int e) {
		dc[i] = 0;
		dl[i] = dr[i] = dd[i] = e - s + 1;
		if (s == e) return;
		int m = (s + e) / 2;
		init(i * 2, s, m);
		init(i * 2 + 1, m + 1, e);
	}
	void init() {
		init(1, 1, M);
	}
	void upd(int i, int s, int e, int p, int q, int r) {
		if (q < p || e < p || q < s) return;
		if (p <= s && e <= q) {
			dc[i] += r;
			if (dc[i]) {
				dl[i] = dr[i] = dd[i] = 0;
			}
			else {
				if (s == e) {
					dl[i] = dr[i] = dd[i] = 1;
				}
				else {
					int m = (s + e) / 2;
					int ll = (m - s + 1), rl = (e - m);
					dl[i] = dl[i * 2];
					if (dd[i * 2] == ll) upmax(dl[i], ll + dl[i * 2 + 1]);
					dr[i] = dr[i * 2 + 1];
					if (dd[i * 2 + 1] == rl) upmax(dr[i], rl + dr[i * 2]);
					dd[i] = max({ dl[i], dr[i], dd[i * 2], dd[i * 2 + 1], dr[i * 2] + dl[i * 2 + 1] });
				}
			}
			return;
		}
		int m = (s + e) / 2;
		upd(i * 2, s, m, p, q, r);
		upd(i * 2 + 1, m + 1, e, p, q, r);

		if (dc[i]) {
			dl[i] = dr[i] = dd[i] = 0;
		}
		else {
			int ll = (m - s + 1), rl = (e - m);
			dl[i] = dl[i * 2];
			if (dd[i * 2] == ll) upmax(dl[i], ll + dl[i * 2 + 1]);
			dr[i] = dr[i * 2 + 1];
			if (dd[i * 2 + 1] == rl) upmax(dr[i], rl + dr[i * 2]);
			dd[i] = max({ dl[i], dr[i], dd[i * 2], dd[i * 2 + 1], dr[i * 2] + dl[i * 2 + 1] });
		}
	}
	void upd(int s, int e, int r) {
		upd(1, 1, M, s, e, r);
	}
	int get() {
		return dd[1];
	}
} seg;




int SX[MAXK], EX[MAXK], SY[MAXK], EY[MAXK], A[MAXK];

int N, M, K, B;



int doTC2() {
	seg.M = ::N;
	seg.init();

	vector<EVT> IV, OV;
	for (int i = 1; i <= K; i++) {
		IV.emplace_back(1, SX[i], SY[i], EY[i], 1);
		OV.emplace_back(2, EX[i] + 1, SY[i], EY[i], -1);
	}
	sorv(IV);
	sorv(OV);

	vector<int> VX;
	VX.pb(1);
	for (int i = 1, t; i <= K; i++) {
		t = EX[i] + 1;
		if (M < t) continue;
		VX.pb(t);
	}
	sorv(VX); univ(VX);

	int ret = 0;

	for (int sx = 1, ex = 1, sxi = 0, ivi = 0, ovi = 0; sxi < sz(VX); sxi++) {
		sx = VX[sxi]; upmax(ex, sx);

		//printf("sx=%d, ex=%d : ret=%d\n", sx, ex, ret);

		for (; ivi < sz(IV) && IV[ivi].x <= sx; ivi++) {
			seg.upd(IV[ivi].a, IV[ivi].b, IV[ivi].c);
		}
		for (; ovi < sz(OV) && OV[ovi].x <= sx; ovi++) {
			seg.upd(OV[ovi].a, OV[ovi].b, OV[ovi].c);
		}
		for (; ex <= M;) {
			int t = seg.get();
			if (t < ex - sx + 1) break;
			upmax(ret, ex - sx + 1);
			ex++;
			for (; ivi < sz(IV) && IV[ivi].x <= ex; ivi++) {
				seg.upd(IV[ivi].a, IV[ivi].b, IV[ivi].c);
			}
		}
	}

	return ret;
}




bool isPossibleTC1(int L) {
	tc1seg.init();
	tc1seg.M = ::N;
	vector<EVTTC1> EV;
	EV.emplace_back(3, 1, 0, 0, 0);
	for (int i = 1, t; i <= K; i++) {
		t = EX[i] + 1;
		if (M < t + L - 1) continue;
		EV.emplace_back(3, t, 0, 0, 0);
	}
	for (int i = 1; i <= K; i++) {
		EV.emplace_back(1, max(1, SX[i] - L + 1), max(1, SY[i] - L + 1), EY[i], A[i]);
		EV.emplace_back(2, EX[i] + 1, max(1, SY[i] - L + 1), EY[i], -A[i]);
	}
	sorv(EV);

	ll ret = INFLL;

	for (auto &e : EV) {
		if (e.type < 3) {
			//printf("UPD %d : %d %d %d\n", e.x, e.a, e.b, e.c);
			tc1seg.upd(e.a, e.b, e.c);
		}
		else {
			//printf("QUR %d : %d %d :: %lld\n", e.x, 1, N - L + 1, tc1seg.get(1, N-L+1));
			upmin(ret, tc1seg.get(1, N-L+1));
		}
	}

	//printf("L=%d, ret=%lld\n", L, ret);

	return ret <= B;
}
int doTC1() {
	if (!isPossibleTC1(1)) return 0;
	int s = 1, e = min(N, M); for (int m, t; s < e;) {
		m = (s + e + 1) / 2;
		t = isPossibleTC1(m);
		//printf("%d %d %d : %d\n", s, e, m, t);
		if(t) s = m;
		else e = m - 1;
	}
	return s;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);

	cin >> M >> N >> B >> K;
	for (int i = 1; i <= K; i++) {
		cin >> SX[i] >> SY[i] >> EX[i] >> EY[i] >> A[i];
		//printf("%d : %d %d %d %d\n", i, SX[i], EX[i], SY[i], EY[i]);
	}

	if (B) {
		cout << doTC1() << endl;
	}
	else {
		cout << doTC2() << endl;
	}

	//while (getchar());

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 96092 KB Output is correct
2 Correct 82 ms 96116 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 96160 KB Output is correct
2 Correct 84 ms 96160 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 96160 KB Output is correct
2 Correct 300 ms 96160 KB Output is correct
3 Correct 277 ms 96160 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 96160 KB Output is correct
2 Correct 747 ms 96160 KB Output is correct
3 Correct 677 ms 96160 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 96160 KB Output is correct
2 Correct 247 ms 96160 KB Output is correct
3 Correct 534 ms 96160 KB Output is correct
4 Correct 1485 ms 96160 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1629 ms 96160 KB Output is correct
2 Correct 1540 ms 96160 KB Output is correct
3 Correct 1164 ms 96160 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 96160 KB Output is correct
2 Correct 1871 ms 96160 KB Output is correct
3 Correct 1945 ms 96160 KB Output is correct
4 Correct 1932 ms 96160 KB Output is correct
5 Correct 2198 ms 96160 KB Output is correct
6 Correct 1461 ms 96160 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 109732 KB Output is correct
2 Correct 394 ms 109732 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 117700 KB Output is correct
2 Correct 1281 ms 118136 KB Output is correct
3 Correct 873 ms 118136 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1592 ms 123548 KB Output is correct
2 Correct 1863 ms 123548 KB Output is correct
3 Correct 1926 ms 123548 KB Output is correct
4 Correct 1664 ms 123548 KB Output is correct
5 Correct 1014 ms 123548 KB Output is correct