oj.uz

Submission #54208

# Submission time Handle Problem Language Result Execution time Memory
54208 2018-07-02T19:38:21 Z baactree Pyramid Base (IOI08_pyramid_base) C++17
35 / 100
 3947 ms 58952 KB 
#include <bits/stdc++.h>
using namespace std;
namespace fio {
	const int BSIZE = 1 << 17;
	unsigned char buffer[BSIZE];
	auto p = buffer + BSIZE;
	inline unsigned char readChar() {
		if (p == buffer + BSIZE) {
			fread(buffer, 1, BSIZE, stdin);
			p = buffer;
		}
		return *p++;
	}
	int readInt() {
		unsigned char c = readChar();
		while (c < '-') {
			c = readChar();
		}
		int ret = 0;
		while (c >= '-') {
			ret = ret * 10 + c - '0';
			c = readChar();
		}
		return ret;
	}
}
typedef long long ll;
ll tree[1 << 21][2];
const ll inf = 0x3f3f3f3f3f3f3f3f;
void push(int nodele, int noderi, int node) {
	tree[node][0] += tree[node][1];
	if (nodele != noderi) {
		tree[node * 2][1] += tree[node][1];
		tree[node * 2 + 1][1] += tree[node][1];
	}
	tree[node][1] = 0;
}
void update(int le, int ri, ll val, int nodele, int noderi, int node) {
	if (tree[node][1])push(nodele, noderi, node);
	if (le > noderi || ri < nodele)return;
	if (le <= nodele && noderi <= ri) {
		tree[node][1] = val;
		push(nodele, noderi, node);
		return;
	}
	int mid = (nodele + noderi) / 2;
	update(le, ri, val, nodele, mid, node * 2);
	update(le, ri, val, mid + 1, noderi, node * 2 + 1);
	tree[node][0] = min(tree[node * 2][0], tree[node * 2 + 1][0]);
}
ll query(int le, int ri, int nodele, int noderi, int node) {
	if (tree[node][1])push(nodele, noderi, node);
	if (le > noderi || ri < nodele)return inf;
	if (le <= nodele && noderi <= ri)return tree[node][0];
	int mid = (nodele + noderi) / 2;
	return min(query(le, ri, nodele, mid, node * 2), query(le, ri, mid + 1, noderi, node * 2 + 1));
}
int n, m, b, p;
vector<tuple<int, int, int> > vec[1000005];
int btree[1000005];
void bupdate(int idx, int val,int k) {
	while (idx <= m - k + 1) {
		btree[idx] += val;
		idx += idx & (-idx);
	}
}
int bquery(int idx) {
	int ret = 0;
	while (idx) {
		ret += btree[idx];
		idx -= idx & (-idx);
	}
	return ret;
}
bool possi(int k) {
	if(b)memset(tree, 0, sizeof(tree));
	else {
		for (int i = 1; i <= m - k + 1; i++)
			btree[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (auto v : vec[i]) {
			int y1, y2, c;
			tie(y1, y2, c) = v;
			if (c > 0) {
				if (b)update(max(1, y1 - k + 1), min(m - k + 1, y2), c, 1, m - k + 1, 1);
				else {
					bupdate(max(1, y1 - k + 1), 1, k);
					bupdate(min(m - k + 1, y2) + 1, -1, k);
				}
			}
		}
		if (i >= k) {
			for (auto v : vec[i - k]) {
				int y1, y2, c;
				tie(y1, y2, c) = v;
				if (c < 0) {
					if (b)update(max(1, y1 - k + 1), min(m - k + 1, y2), c, 1, m - k + 1, 1);
					else {
						bupdate(max(1, y1 - k + 1), 1, k);
						bupdate(min(m - k + 1, y2) + 1, -1, k);
					}
				}
			}
		}
		if (i >= k && (b ? query(1, m - k + 1, 1, m - k + 1, 1) <= b : bquery(m - k + 1) == m - k + 1)) return true;
	}
	return false;
}
int main() {
	//scanf("%d%d%d%d", &n, &m, &b, &p);
	n = fio::readInt();
	m = fio::readInt();
	b = fio::readInt();
	p = fio::readInt();
	for (int i = 0; i < p; i++) {
		int x1, y1, x2, y2, c;
		//scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
		x1 = fio::readInt();
		y1 = fio::readInt();
		x2 = fio::readInt();
		y2 = fio::readInt();
		c = fio::readInt();
		vec[x1].emplace_back(y1, y2, b ? c : 1);
		vec[x2].emplace_back(y1, y2, b ? -c : -1);
	}
	int le, ri, ans, mid;
	le = 1;
	ri = m;
	ans = 0;
	while (le <= ri) {
		mid = (le + ri) / 2;
		if (possi(mid)) {
			ans = mid;
			le = mid + 1;
		}
		else ri = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

pyramid_base.cpp: In function 'unsigned char fio::readChar()':
pyramid_base.cpp:9:9: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    fread(buffer, 1, BSIZE, stdin);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 292 ms 28032 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 148 ms 57128 KB Output is correct
2 Correct 239 ms 57328 KB Output is correct
3 Correct 187 ms 57328 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 57768 KB Output is correct
2 Correct 674 ms 57920 KB Output is correct
3 Correct 507 ms 57920 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 58188 KB Output is correct
2 Correct 115 ms 58304 KB Output is correct
3 Correct 786 ms 58304 KB Output is correct
4 Correct 818 ms 58304 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 58320 KB Output is correct
2 Correct 1556 ms 58400 KB Output is correct
3 Correct 419 ms 58576 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 58576 KB Output is correct
2 Correct 2017 ms 58832 KB Output is correct
3 Correct 1934 ms 58832 KB Output is correct
4 Correct 2005 ms 58832 KB Output is correct
5 Correct 1976 ms 58832 KB Output is correct
6 Correct 404 ms 58952 KB Output is correct

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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