oj.uz

Submission #157086

# Submission time Handle Problem Language Result Execution time Memory
157086 2019-10-09T12:32:53 Z youngyojun Pyramid Base (IOI08_pyramid_base) C++11
100 / 100
 1781 ms 134476 KB 
#include <bits/stdc++.h>
#define eb emplace_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;

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<<1], d[i<<1|1]) + TC1SEG::e[i];
			return;
		}
		int m = s+e >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|1, m+1, e, p, q, r);
		d[i] = min(d[i<<1], d[i<<1|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 >> 1;
		return min(get(i<<1, s, m, p, q), get(i<<1|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 {
		return x != t.x ? x < t.x : 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 {
		return x != t.x ? x < t.x : 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 >> 1;
		init(i<<1, s, m);
		init(i<<1|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 >> 1;
					int ll = m-s+1, rl = e-m;
					dl[i] = dl[i<<1];
					if(dd[i<<1] == ll) upmax(dl[i], ll + dl[i<<1|1]);
					dr[i] = dr[i<<1|1];
					if(dd[i<<1|1] == rl) upmax(dr[i], rl + dr[i<<1]);
					dd[i] = max({ dl[i], dr[i], dd[i<<1], dd[i<<1|1], dr[i<<1] + dl[i<<1|1] });
				}
			}
			return;
		}
		int m = s+e >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|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<<1];
			if(dd[i<<1] == ll) upmax(dl[i], ll + dl[i<<1|1]);
			dr[i] = dr[i<<1|1];
			if(dd[i<<1|1] == rl) upmax(dr[i], rl + dr[i<<1]);
			dd[i] = max({ dl[i], dr[i], dd[i<<1], dd[i<<1|1], dr[i<<1] + dl[i<<1|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.eb(1, SX[i], SY[i], EY[i], 1);
		OV.eb(2, EX[i]+1, SY[i], EY[i], -1);
	}
	sorv(IV); sorv(OV);

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

	int ret = 0;
	for(int sx = 1, ex = 1, sxi = 0, ivi = 0, ovi = 0, n = sz(VX), ivn = sz(IV), ovn = sz(OV); sxi < n; sxi++) {
		sx = VX[sxi]; upmax(ex, sx);
		for(; ivi < ivn && IV[ivi].x <= sx; ivi++)
			seg.upd(IV[ivi].a, IV[ivi].b, IV[ivi].c);
		for(; ovi < ovn && OV[ovi].x <= sx; ovi++)
			seg.upd(OV[ovi].a, OV[ovi].b, OV[ovi].c);
		for(int t; ex <= M;) {
			t = seg.get();
			if(t < ex-sx+1) break;
			upmax(ret, ex-sx+1);
			ex++;
			for(; ivi < ivn && 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.eb(3, 1, 0, 0, 0);
	for(int i = 1, t; i <= K; i++) {
		t = EX[i]+1;
		if (M < t+L-1) continue;
		EV.eb(3, t, 0, 0, 0);
	}
	for(int i = 1; i <= K; i++) {
		EV.eb(1, max(1, SX[i]-L+1), max(1, SY[i]-L+1), EY[i], A[i]);
		EV.eb(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) tc1seg.upd(e.a, e.b, e.c);
		else upmin(ret, tc1seg.get(1, N-L+1));
	}
	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 >> 1;
		t = isPossibleTC1(m);
		if(t) s = m;
		else e = m-1;
	}
	return s;
}

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

	cin >> M >> N >> B >> K;
	for(int i = 1; i <= K; i++)
		cin >> SX[i] >> SY[i] >> EX[i] >> EY[i] >> A[i];

	cout << (B ? doTC1() : doTC2()) << endl;
	return 0;
}

Compilation message

pyramid_base.cpp: In member function 'void TC1SEG::upd(int, int, int, int, int, int)':
pyramid_base.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
pyramid_base.cpp: In member function 'll TC1SEG::get(int, int, int, int, int)':
pyramid_base.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
pyramid_base.cpp: In member function 'void SEG::init(int, int, int)':
pyramid_base.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
pyramid_base.cpp: In member function 'void SEG::upd(int, int, int, int, int, int)':
pyramid_base.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int m = s+e >> 1;
              ~^~
pyramid_base.cpp:98:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
pyramid_base.cpp: In function 'int doTC1()':
pyramid_base.cpp:184:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   m = s+e+1 >> 1;
       ~~~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 96012 KB Output is correct
2 Correct 94 ms 95992 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 95988 KB Output is correct
2 Correct 97 ms 95992 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 63872 KB Output is correct
2 Correct 292 ms 63880 KB Output is correct
3 Correct 265 ms 63920 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 65836 KB Output is correct
2 Correct 634 ms 66040 KB Output is correct
3 Correct 612 ms 66044 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1042 ms 66384 KB Output is correct
2 Correct 237 ms 66396 KB Output is correct
3 Correct 525 ms 66204 KB Output is correct
4 Correct 1228 ms 66660 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 68112 KB Output is correct
2 Correct 1366 ms 68400 KB Output is correct
3 Correct 1076 ms 66920 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1371 ms 68644 KB Output is correct
2 Correct 1628 ms 69068 KB Output is correct
3 Correct 1781 ms 69056 KB Output is correct
4 Correct 1697 ms 69072 KB Output is correct
5 Correct 1708 ms 68944 KB Output is correct
6 Correct 1106 ms 68408 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 879 ms 115120 KB Output is correct
2 Correct 388 ms 86076 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1127 ms 126100 KB Output is correct
2 Correct 1093 ms 125704 KB Output is correct
3 Correct 776 ms 125272 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1430 ms 134476 KB Output is correct
2 Correct 1738 ms 133944 KB Output is correct
3 Correct 1687 ms 133636 KB Output is correct
4 Correct 1485 ms 133496 KB Output is correct
5 Correct 995 ms 133680 KB Output is correct