oj.uz

Submission #54200

# Submission time Handle Problem Language Result Execution time Memory
54200 2018-07-02T19:14:54 Z baactree Pyramid Base (IOI08_pyramid_base) C++17
0 / 100
 5000 ms 103128 KB 
#include <bits/stdc++.h>
using namespace std;
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> > in[1000005],out[1000005];
vector<int> x;
bool possi(int k) {
	memset(tree, 0, sizeof(tree));
	for(auto xx:x) {
		for (auto v : in[xx]) {
			int y1, y2, c;
			tie(y1, y2, c) = v;
			update(max(1, y1 - k + 1), min(m - k + 1, y2), c,1,m,1);
		}
		if (xx >= k) {
			for (auto v : out[xx - k]) {
				int y1, y2, c;
				tie(y1, y2, c) = v;
				update(max(1, y1 - k + 1), min(m - k + 1, y2), c, 1, m, 1);
			}
		}
		if (xx >= k && query(1, m - k + 1, 1, m, 1) <= b) return true;
	}
	return false;
}
int main() {
	scanf("%d%d%d%d", &n, &m, &b, &p);
	for (int i = 0; i < p; i++) {
		int x1, y1, x2, y2, c;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
		in[x1].emplace_back(y1, y2, c);
		out[x2].emplace_back(y1, y2, -c);
		x.push_back(x1);
	}
	sort(x.begin(), x.end());
	x.erase(unique(x.begin(), x.end()), x.end());
	int le, ri, ans, mid;
	le = 1;
	ri = min(n, 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 'int main()':
pyramid_base.cpp:57: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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 92592 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 5021 ms 97964 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 5029 ms 103128 KB Time limit exceeded
2 Halted 0 ms 0 KB -