Submission #560338

#TimeUsernameProblemLanguageResultExecution timeMemory
560338SSRSPyramid Base (IOI08_pyramid_base)C++14
70 / 100
5073 ms111528 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1000000000000; struct lazy_segment_tree{ int N; vector<long long> ST, lazy; lazy_segment_tree(int N2){ N = 1; while (N < N2){ N *= 2; } ST = vector<long long>(N * 2 - 1, INF); for (int i = 0; i < N2; i++){ ST[N - 1 + i] = 0; } for (int i = N - 2; i >= 0; i--){ ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]); } lazy = vector<long long>(N * 2 - 1, 0); } void eval(int i){ if (i < N - 1){ lazy[i * 2 + 1] += lazy[i]; lazy[i * 2 + 2] += lazy[i]; } ST[i] += lazy[i]; lazy[i] = 0; } void range_add(int L, int R, int x, int i, int l, int r){ eval(i); if (r <= L || R <= l){ return; } else if (L <= l && r <= R){ lazy[i] += x; eval(i); } else { int m = (l + r) / 2; range_add(L, R, x, i * 2 + 1, l, m); range_add(L, R, x, i * 2 + 2, m, r); ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]); } } void range_add(int L, int R, int x){ range_add(L, R, x, 0, 0, N); } long long all(){ eval(0); return ST[0]; } }; int main(){ ios::sync_with_stdio(false); int M, N; cin >> M >> N; int B; cin >> B; int P; cin >> P; vector<int> X1(P), Y1(P), X2(P), Y2(P), C(P); for (int i = 0; i < P; i++){ cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> C[i]; X1[i]--; Y1[i]--; } int tv = 0, fv = min(M, N) + 1; while (fv - tv > 1){ int mid = (tv + fv) / 2; vector<vector<int>> add(N - mid + 2), sub(N - mid + 2); for (int i = 0; i < P; i++){ add[max(Y1[i] - mid + 1, 0)].push_back(i); sub[min(Y2[i], N - mid + 1)].push_back(i); } lazy_segment_tree ST(M - mid + 1); bool ok = false; for (int i = 0; i < N - mid + 1; i++){ for (int j : add[i]){ ST.range_add(max(X1[j] - mid + 1, 0), min(X2[j], M - mid + 1), C[j]); } for (int j : sub[i]){ ST.range_add(max(X1[j] - mid + 1, 0), min(X2[j], M - mid + 1), -C[j]); } if (ST.all() <= B){ ok = true; } } if (ok){ tv = mid; } else { fv = mid; } } cout << tv << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...