oj.uz

Submission #54001

# Submission time Handle Problem Language Result Execution time Memory
54001 2018-07-02T07:51:29 Z 윤교준(#1456) Pyramid Base (IOI08_pyramid_base) C++11
0 / 100
 1235 ms 55404 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*3], e[MAXM*3];
	void init() {
		fill(d, d + MAXM * 3, INFLL);
		fill(e, e + MAXM * 3, 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;
			d[i] += r;
			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, MAXM-1, p, q, r);
	}
	ll get() {
		return d[1];
	}
} 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();
	vector<EVTTC1> EV;
	EV.emplace_back(3, 0, 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) {
			tc1seg.upd(e.a, e.b, e.c);
		}
		else {
			upmin(ret, tc1seg.get());
		}
	}

	return ret <= B;
}
int doTC1() {
	int s = 0, 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);
	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];
	}

	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 33 ms 47352 KB Output isn't correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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