Submission #72714

#	Time	Username	Problem	Language	Result	Execution time	Memory
72714		kingpig9	Pyramid Base (IOI08_pyramid_base)	C++11	70 / 100	5033 ms	66740 KiB

pyramid_base

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

const int MAXN = 1 << 20;
const ll INF = 1e10;

struct segtree {
	ll tree[2 * MAXN];
	ll lazy[2 * MAXN];

	void reset() {
		for (int i = 0; i < 2 * MAXN; i++) {
			tree[i] = lazy[i] = 0;
		}
	}

	void put (int cur, ll v) {
		tree[cur] += v;
		lazy[cur] += v;
	}

	void down (int cur) {
		if (lazy[cur]) {
			put(2 * cur, lazy[cur]);
			put(2 * cur + 1, lazy[cur]);
			lazy[cur] = 0;
		}
	}

	void update (int a, int b, ll v, int cur = 1, int lt = 0, int rt = MAXN) {
		/*
		if (lt == 0 && rt == MAXN) {
			debug("update(%d, %d, %lld)\n", a, b, v);
		}
		*/
		if (rt <= a || b <= lt) {
			return;
		}

		if (a <= lt && rt <= b) {
			put(cur, v);
			return;
		}
		down(cur);

		int mid = (lt + rt) / 2;
		update(a, b, v, 2 * cur, lt, mid);
		update(a, b, v, 2 * cur + 1, mid, rt);
		tree[cur] = min(tree[2 * cur], tree[2 * cur + 1]);
	}
};

struct rect {
	int x1, y1, x2, y2;
	ll cost;

	void read() {
		scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &cost);
		x1--;
		y1--;
	}
};

int N, M, B;
int P;
rect A[MAXN], srtx1[MAXN], srtx2[MAXN];

bool cmpx1 (rect r, rect s) {
	return r.x1 < s.x1;
}

bool cmpx2 (rect r, rect s) {
	return r.x2 < s.x2;
}

segtree seg;

bool moo (int mid) {
	//add infinity rectangle
	//RESET the segtree
	seg.reset();

	seg.update(M - mid + 1, MAXN, INF);
	int ptrx1 = 0, ptrx2 = 0;

	for (int x = 0; x + mid <= N; x++) {
		for (; ptrx1 < P && max(0, srtx1[ptrx1].x1 - mid + 1) == x; ptrx1++) {
			//add the rectangle
			seg.update(max(0, srtx1[ptrx1].y1 - mid + 1), srtx1[ptrx1].y2, srtx1[ptrx1].cost);
			//debug("add rectangle (%d, %d, %d, %d)\n", srtx1[ptrx1].x1, srtx1[ptrx1].y1, srtx1[ptrx1].x2, srtx1[ptrx1].y2);
			//debug("bottom d %d\n", max(0, srtx1[ptrx1].y1 - P + 1));
		}

		for (; ptrx2 < P && srtx2[ptrx2].x2 == x; ptrx2++) {
			//delete the rectangle
			seg.update(max(0, srtx2[ptrx2].y1 - mid + 1), srtx2[ptrx2].y2, -srtx2[ptrx2].cost);
			//debug("del rectangle (%d, %d, %d, %d)\n", srtx2[ptrx2].x1, srtx2[ptrx2].y1, srtx2[ptrx2].x2, srtx2[ptrx2].y2);
		}

		//query.
		if (seg.tree[1] <= B) {
			return true;
		}
	}

	return false;
}

void read_input() {
	//read raw input
	scanf("%d %d %d %d", &N, &M, &B, &P);
	for (int i = 0; i < P; i++) {
		A[i].read();
		srtx1[i] = srtx2[i] = A[i];
	}

	//sort by x1
	sort(srtx1, srtx1 + P, cmpx1);

	//sort by x2
	sort(srtx2, srtx2 + P, cmpx2);
}

int main() {
	read_input();
	//assert(moo(3));

	int lo = 0, hi = min(N, M) + 1;
	while (hi - lo > 1) {
		int mid = (lo + hi) / 2;
		if (moo(mid)) {
			lo = mid;
		} else {
			hi = mid;
		}
	}
	printf("%d\n", lo);
}

Compilation message (stderr)

pyramid_base.cpp: In function 'void read_input()':
pyramid_base.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &N, &M, &B, &P);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In member function 'void rect::read()':
pyramid_base.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d %lld", &x1, &y1, &x2, &y2, &cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10