oj.uz

Submission #794182

# Submission time Handle Problem Language Result Execution time Memory
794182 2023-07-26T10:20:15 Z rxlfd314 Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 118516 KB 
#include <bits/stdc++.h>
using namespace std;

struct Segtree {
	vector<int> ladd, sgt;
	Segtree(int N) {
		ladd.resize(N<<2, 0);
		sgt.resize(N<<2, 0);
	}
	void push(int i) {
		if (!ladd[i]) return;
		ladd[i<<1] += ladd[i];
		ladd[i<<1|1] += ladd[i];
		sgt[i<<1] += ladd[i];
		sgt[i<<1|1] += ladd[i];
		ladd[i] = 0;
	}
	void radd(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
		if (tr < 0) tr += sgt.size() >> 2;
		if (tl > qr || tr < ql) return;
		if (ql <= tl && tr <= qr) {
			sgt[i] += v, ladd[i] += v;
		} else {
			push(i);
			int mid = tl + tr >> 1;
			radd(ql, qr, v, i<<1, tl, mid);
			radd(ql, qr, v, i<<1|1, mid+1, tr);
			sgt[i] = min(sgt[i<<1], sgt[i<<1|1]);
		}
	}
	int qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
		if (tr < 0) tr += sgt.size() >> 2;
		if (tl > qr || tr < ql) return INT_MAX;
		if (ql <= tl && tr <= qr) return sgt[i];
		push(i);
		int mid = tl + tr >> 1;
		return min(qry(ql, qr, i<<1, tl, mid), qry(ql, qr, i<<1|1, mid+1, tr));
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, M, B, P;
	cin >> N >> M >> B >> P;
	vector<vector<int>> A(P, vector<int>(5));
	for (auto &v : A) {
		for (int &i : v) {
			cin >> i, i--;
		}
		v[4]++;
	}
	if (1) {
		int lo = 0, hi = min(N, M);
		while (lo < hi) {
			int mid = lo + hi + 1 >> 1;
			vector<vector<int>> evs;
			for (auto &v : A) {
				evs.push_back({v[0], max(0, v[1]-mid+1), min(M-mid, v[3]), v[4]});
				if (v[2] + mid < N) {
					evs.push_back({v[2] + mid, max(0, v[1]-mid+1), min(M-mid, v[3]), -v[4]});
				}
			}
			sort(evs.begin(), evs.end());
			Segtree sgt(M-mid+1);
			bool can = false;
			for (int i = mid-1, j = 0; i < N; i++) {
				for (; j < evs.size() && evs[j][0] <= i; j++) {
					sgt.radd(evs[j][1], evs[j][2], evs[j][3]);
				}
				can |= sgt.qry(0, M-mid) <= B;
			}
			can ? lo = mid : hi = mid - 1;
		}
		cout << lo << '\n';
	}
}

Compilation message

pyramid_base.cpp: In member function 'void Segtree::radd(int, int, int, int, int, int)':
pyramid_base.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |    int mid = tl + tr >> 1;
      |              ~~~^~~~
pyramid_base.cpp: In member function 'int Segtree::qry(int, int, int, int, int)':
pyramid_base.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = tl + tr >> 1;
      |             ~~~^~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |    int mid = lo + hi + 1 >> 1;
      |              ~~~~~~~~^~~
pyramid_base.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (; j < evs.size() && evs[j][0] <= i; j++) {
      |            ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 820 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3504 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16080 KB Output is correct
2 Correct 311 ms 32028 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 29936 KB Output is correct
2 Correct 50 ms 16084 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1236 KB Output is correct
2 Correct 58 ms 1776 KB Output is correct
3 Correct 48 ms 1668 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 5812 KB Output is correct
2 Correct 291 ms 6672 KB Output is correct
3 Correct 233 ms 6656 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 19200 KB Output is correct
2 Correct 71 ms 5164 KB Output is correct
3 Correct 229 ms 35136 KB Output is correct
4 Correct 888 ms 34528 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 29544 KB Output is correct
2 Correct 953 ms 37740 KB Output is correct
3 Correct 167 ms 19816 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 20932 KB Output is correct
2 Correct 1245 ms 38144 KB Output is correct
3 Correct 1300 ms 38204 KB Output is correct
4 Correct 1237 ms 38108 KB Output is correct
5 Correct 1214 ms 37996 KB Output is correct
6 Correct 133 ms 20600 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 77224 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 5058 ms 109580 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 5059 ms 118516 KB Time limit exceeded
2 Halted 0 ms 0 KB -