Submission #891743

#TimeUsernameProblemLanguageResultExecution timeMemory
891743MackerPyramid Base (IOI08_pyramid_base)C++17
80 / 100
5064 ms143224 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define all(v) v.begin(), v.end() #pragma GCC optimize("Ofast") #pragma GCC target("avx2") int st[2097157]; int lz[2097157]; int len = 1; void init(int n){ len = 1; while(len < n) len *= 2; for (int i = len; i < len + n; i++) { st[i] = 0; lz[i] = 0; } for (int i = len + n; i < 2 * len; i++){ st[i] = INT_MAX; lz[i] = 0; } for (int i = len - 1; i > 0; i--) { st[i] = min(st[i * 2], st[i * 2 + 1]); lz[i] = 0; } } void prop(int i){ st[i * 2] += lz[i]; st[i * 2 + 1] += lz[i]; lz[i * 2] += lz[i]; lz[i * 2 + 1] += lz[i]; lz[i] = 0; } void add(int f, int t, int v, int i = 1, int s = 0, int e = len){ if(f >= e || s >= t) return; if(f <= s && e <= t){ st[i] += v; lz[i] += v; return; } prop(i); add(f, t, v, i * 2, s, (s + e) / 2); add(f, t, v, i * 2 + 1, (s + e) / 2, e); st[i] = min(st[i * 2], st[i * 2 + 1]); } vector<tuple<int, int, int, int>> ev[1000005]; //[y][i] -> t(0s, 1e), x, xx, c bool can(int d, vector<array<int, 5>> v, int w, int h, int b){ w -= d; h -= d; for (auto &i : v) { i[0] = max(0, i[0] - d); i[1] = max(0, i[1] - d); i[2] = min(w - 1, i[2]); i[3] = min(h - 1, i[3]); } init(w); for (int i = 0; i < 1000005; i++) { ev[i] = {}; } for (auto& i : v) { ev[i[1]].push_back({0, i[0], i[2], i[4]}); ev[i[3] + 1].push_back({1, i[0], i[2], i[4]}); } int y = 0; for (auto& es : ev) { for (auto& e : es) { auto& [t, x, xx, c] = e; if(t == 0){ add(x, xx + 1, c); } else{ add(x, xx + 1, -c); } } if(y >= h) break; if(st[1] <= b) return true; y++; } return false; } int main() { int w, h; cin >> w >> h; int b; cin >> b; int n; cin >> n; vector<array<int, 5>> v(n); for (auto &i : v){ cin >> i[0] >> i[1] >> i[2] >> i[3] >> i[4]; for (int j = 0; j < 4; j++) i[j]--; } int l = -1, r = min(w, h), mid; while(l < r){ mid = (l + r + 1) / 2; if(can(mid, v, w, h, b)) l = mid; else r = mid - 1; } cout << l + 1 << 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...