제출 #1042777

#제출 시각아이디문제언어결과실행 시간메모리
1042777gygPyramid Base (IOI08_pyramid_base)C++17
80 / 100
5066 ms170072 KiB
#pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 4e5 + 5, MAX_R = 1e6 + 5, INF = 1e18; int r, c, k, n; array<int, MAX_N> row1, col1, row2, col2, cost; int s; struct Node { int min, lazy; }; array<Node, 4 * MAX_R> st; void propogate(int u) { st[2 * u].min += st[u].lazy, st[2 * u].lazy += st[u].lazy; st[2 * u + 1].min += st[u].lazy, st[2 * u + 1].lazy += st[u].lazy; st[u].lazy = 0; } void update(int l, int _r, int x, int u = 1, int lo = 1, int hi = r - s + 1) { if (l <= lo && hi <= _r) { st[u].min += x, st[u].lazy += x; return; } propogate(u); int mid = (lo + hi) / 2; if (l <= mid) update(l, _r, x, 2 * u, lo, mid); if (mid < _r) update(l, _r, x, 2 * u + 1, mid + 1, hi); st[u].min = min(st[2 * u].min, st[2 * u + 1].min); } array<vector<int>, MAX_R> ins, del; bool check(int _s) { s = _s; Node zero = {0, 0}; fill(st.begin(), st.end(), zero); for (int i = 1; i <= c; i++) ins[i].clear(), del[i].clear(); for (int i = 1; i <= n; i++) { ins[max(col1[i] - s + 1, 1ll)].push_back(i); del[col2[i]].push_back(i); } for (int col = 1; col <= c - s + 1; col++) { for (int i : ins[col]) update(max(row1[i] - s + 1, 1ll), row2[i], cost[i]); if (st[1].min <= k) { // cout << s << " " << col << ": " << query(1, r - s + 1) << endl; return true; } for (int i : del[col]) update(max(row1[i] - s + 1, 1ll), row2[i], -cost[i]); } return false; } int bin_search() { int lo = 1, hi = min(r, c); while (lo != hi) { int mid = ceil((lo + hi) / (double) 2); if (check(mid)) lo = mid; else hi = mid - 1; } if (!check(lo)) return 0; return lo; } signed main() { // freopen("pbs.in", "r", stdin), freopen("pbs.out", "w", stdout); cin.sync_with_stdio(false), cin.tie(0); cin >> r >> c >> k >> n; for (int i = 1; i <= n; i++) cin >> row1[i] >> col1[i] >> row2[i] >> col2[i] >> cost[i]; int ans = bin_search(); cout << ans << '\n'; }
#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...