제출 #1250219

#제출 시각아이디문제언어결과실행 시간메모리
1250219ThunnusPyramid Base (IOI08_pyramid_base)C++20
65 / 100
2574 ms271700 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; #define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define fi first #define se second #define pii pair<int, int> #define sz(x) (int)(x).size() const int M = 1e6 + 5; struct Node{ int val, len, suff, pref, ans, lazy; Node(int v, int l, int s, int p, int a, int lz) : val(v), len(l), suff(s), pref(p), ans(a), lazy(lz) {} Node(int l) : Node(0, l, l, l, l, 0) {} Node() : Node(0, 0, 0, 0, 0, 0) {} }; struct SegTree{ int n; vector<Node> st; SegTree(int n) : n(n), st(4 * n) {} inline Node combine(const Node &a, const Node &b){ Node c; c.len = a.len + b.len; if(a.val > b.val){ c.val = b.val; c.ans = b.ans; c.pref = 0; c.suff = b.suff; } else if(a.val < b.val){ c.val = a.val; c.ans = a.ans; c.pref = a.pref; c.suff = 0; } else{ c.val = a.val; c.suff = b.suff; if(b.ans == b.len){ c.suff = b.ans + a.suff; } c.pref = a.pref; if(a.ans == a.len){ c.pref = a.ans + b.pref; } c.ans = max({a.ans, b.ans, a.suff + b.pref}); } return c; } inline void build(int v, int tl, int tr){ // wtf??????? if(tl == tr){ st[v] = Node(1); return; } int mid = (tl + tr) / 2; build(2 * v, tl, mid); build(2 * v + 1, mid + 1, tr); st[v] = combine(st[2 * v], st[2 * v + 1]); return; } inline void build(){ build(1, 1, n); return; } inline void apply(int v, int val){ st[v].val += val; st[v].lazy += val; return; } inline void propagate(int v){ apply(2 * v, st[v].lazy); apply(2 * v + 1, st[v].lazy); st[v].lazy = 0; return; } inline void update(int ul, int ur, int val, int v, int tl, int tr){ if(ul > tr || tl > ur) return; if(ul <= tl && tr <= ur){ apply(v, val); return; } int mid = (tl + tr) / 2; propagate(v); update(ul, ur, val, 2 * v, tl, mid); update(ul, ur, val, 2 * v + 1, mid + 1, tr); st[v] = combine(st[2 * v], st[2 * v + 1]); return; } inline void update(int ul, int ur, int val){ if(ul > ur) return; update(max(ul + 1, 1ll), min(ur + 1, n), val, 1, 1, n); return; } }; inline void solve(){ int m, n, budget, p; cin >> n >> m >> budget >> p; vector<array<int, 5>> ob(p); for(int i = 0; i < p; i++){ // {x1, y1, x2, y2, c} cin >> ob[i][0] >> ob[i][1] >> ob[i][2] >> ob[i][3] >> ob[i][4]; ob[i][0]--, ob[i][1]--, ob[i][2]--, ob[i][3]--; } auto solve0 = [&]() -> int { vvi add(n), er(n); for(int i = 0; i < p; i++){ add[ob[i][0]].emplace_back(i); er[ob[i][2]].emplace_back(i); } int ans = 0; SegTree st(m); st.build(); for(int le = 0, ri = -1; le < n; le++){ while(ri < n){ if(st.st[1].val || st.st[1].ans < ri - le + 1) break; ri++; for(int &idx : add[ri]){ array<int, 5> r = ob[idx]; st.update(r[1], r[3], 1); } } ans = max(ans, (ri - 1) - le + 1); // just before the last addition on ri for(int &idx : er[le]){ array<int, 5> r = ob[idx]; st.update(r[1], r[3], -1); } } return ans; }; auto solve1 = [&]() -> int { auto check = [&](int len) -> bool { //cout << "len: " << len << "\n"; vvi pos(n + 1); SegTree st(m - len + 1); for(int i = 0; i < p; i++){ int lx = max(ob[i][0] - len + 1, 0ll), rx = ob[i][2]; pos[lx].emplace_back(i), pos[rx + 1].emplace_back(i); } for(int i = 0; i < n - len + 1; i++){ for(int &idx : pos[i]){ int dy = max(ob[idx][1] - len + 1, 0ll), uy = ob[idx][3], c = (i == ob[idx][2] + 1 ? -ob[idx][4] : ob[idx][4]); //cout << "idx: " << idx << " dy: " << dy << " uy: " << uy << " c: " << c << "\n"; st.update(dy, uy, c); } if(st.st[1].val <= budget) return true; } return false; }; auto bs = [&]() -> int { int lo = 1, hi = min(n, m), ret = 0, mid; while(hi >= lo){ mid = lo + (hi - lo) / 2; if(check(mid)){ lo = mid + 1; ret = mid; } else{ hi = mid - 1; } } return ret; }; return bs(); }; cout << (budget ? solve1() : solve0()) << "\n"; return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }
#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...