oj.uz

Submission #54007

# Submission time Handle Problem Language Result Execution time Memory
54007 2018-07-02T08:11:43 Z 윤교준(#1456) Pyramid Base (IOI08_pyramid_base) C++11
35 / 100
 2084 ms 71124 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 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;
	}
};

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

int N, M, K, B;

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 doTC2() {
	return 0;
}

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 62968 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 62968 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 63004 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 63132 KB Output isn't correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 63132 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 63176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 63388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 63896 KB Output is correct
2 Correct 297 ms 63972 KB Output is correct
3 Correct 288 ms 63972 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 65824 KB Output is correct
2 Correct 699 ms 65860 KB Output is correct
3 Correct 700 ms 65860 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 65980 KB Output is correct
2 Correct 262 ms 66136 KB Output is correct
3 Correct 604 ms 66136 KB Output is correct
4 Correct 1309 ms 66220 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1420 ms 67664 KB Output is correct
2 Correct 1450 ms 67940 KB Output is correct
3 Correct 1058 ms 67940 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 68040 KB Output is correct
2 Correct 1739 ms 68416 KB Output is correct
3 Correct 2084 ms 68416 KB Output is correct
4 Correct 1961 ms 68416 KB Output is correct
5 Correct 1955 ms 68416 KB Output is correct
6 Correct 1231 ms 68416 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 68416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 69100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 281 ms 71124 KB Output isn't correct
2 Halted 0 ms 0 KB -