oj.uz

Submission #72714

# Submission time Handle Problem Language Result Execution time Memory
72714 2018-08-26T19:08:58 Z kingpig9 Pyramid Base (IOI08_pyramid_base) C++11
70 / 100
 5000 ms 66740 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 57 ms 33144 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 33380 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 33380 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 33496 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 33496 KB Output is correct
2 Correct 263 ms 33496 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 33496 KB Output is correct
2 Correct 202 ms 33572 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 33852 KB Output is correct
2 Correct 193 ms 33856 KB Output is correct
3 Correct 161 ms 33856 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 34540 KB Output is correct
2 Correct 535 ms 34652 KB Output is correct
3 Correct 404 ms 34940 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 35372 KB Output is correct
2 Correct 109 ms 35372 KB Output is correct
3 Correct 310 ms 35884 KB Output is correct
4 Correct 764 ms 36460 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 36760 KB Output is correct
2 Correct 1204 ms 36888 KB Output is correct
3 Correct 513 ms 36888 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 37160 KB Output is correct
2 Correct 1407 ms 37164 KB Output is correct
3 Correct 1345 ms 38020 KB Output is correct
4 Correct 1357 ms 39032 KB Output is correct
5 Correct 1524 ms 39868 KB Output is correct
6 Correct 632 ms 40768 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 52724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 59764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5033 ms 66740 KB Time limit exceeded
2 Halted 0 ms 0 KB -