Submission #520576

#TimeUsernameProblemLanguageResultExecution timeMemory
520576lohachoPyramid Base (IOI08_pyramid_base)C++14
100 / 100
1996 ms147152 KiB
#include <bits/stdc++.h> #define int long long #define mi(x, y) (x = min(x, y)) #define ma(x, y) (x = max(x, y)) using namespace std; const int NS = (int)8e5 + 54; int tr[NS * 4], tr2[NS * 4], l[NS * 4], r[NS * 4]; vector<int> srt; struct Data{ int xs, ys, ye, v; Data(){} Data(int xs, int ys, int ye, int v):xs(xs), ys(ys), ye(ye), v(v){} bool operator<(const Data&r)const{ return xs < r.xs || (xs == r.xs && v > r.v); } }; void build(int x, int s, int e){ if(s == e){ tr[x] = l[x] = r[x] = srt[s + 1] - srt[s]; return; } int m = s + e >> 1; build(x * 2, s, m), build(x * 2 + 1, m + 1, e); tr[x] = l[x] = r[x] = tr[x * 2] + tr[x * 2 + 1]; } void push(int x, int s, int e, int ps, int pe, int val){ //cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << endl; if(pe < s || ps > e) return; if(ps <= s && pe >= e){ tr2[x] += val; if(!tr2[x]){ if(s == e) tr[x] = l[x] = r[x] = srt[s + 1] - srt[s]; else{ tr[x] = max({tr[x * 2], tr[x * 2 + 1], r[x * 2] + l[x * 2 + 1]}); l[x] = (tr[x * 2] == srt[(s + e) / 2 + 1] - srt[s] ? tr[x * 2] + l[x * 2 + 1] : l[x * 2]); r[x] = (tr[x * 2 + 1] == srt[e + 1] - srt[(s + e) / 2 + 1] ? tr[x * 2 + 1] + r[x * 2] : r[x * 2 + 1]); } } else{ tr[x] = l[x] = r[x] = 0; } return; } int m = s + e >> 1; push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val); if(!tr2[x]){ if(s == e) tr[x] = l[x] = r[x] = srt[s + 1] - srt[s]; else{ tr[x] = max({tr[x * 2], tr[x * 2 + 1], r[x * 2] + l[x * 2 + 1]}); l[x] = (tr[x * 2] == srt[(s + e) / 2 + 1] - srt[s] ? tr[x * 2] + l[x * 2 + 1] : l[x * 2]); r[x] = (tr[x * 2 + 1] == srt[e + 1] - srt[(s + e) / 2 + 1] ? tr[x * 2 + 1] + r[x * 2] : r[x * 2 + 1]); } } else{ tr[x] = l[x] = r[x] = 0; } } struct Seg{ int n; vector<int> tree, lazy; Seg(int N):n(N){ tree.resize(n * 4), lazy.resize(n * 4); } void add(int x, int l, int r, int val){ lazy[x] += val; tree[x] += val; } void update(int x, int l, int r){ if(lazy[x] == 0) return; int mid = (l + r) >> 1; add(x * 2, l, mid, lazy[x]), add(x * 2 + 1, mid + 1, r, lazy[x]); lazy[x] = 0; } void push(int x, int l, int r, int pl, int pr, int val){ if(pr < l || pl > r || pl > pr) return; if(l >= pl && r <= pr){ add(x, l, r, val); return; } update(x, l, r); int mid = (l + r) >> 1; push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val); tree[x] = min(tree[x * 2], tree[x * 2 + 1]); } int get(int x, int l, int r, int fl, int fr){ if(fr < l || fl > r || fl > fr) return (int)1e9; if(l >= fl && r <= fr) return tree[x]; update(x, l, r); int mid = (l + r) >> 1; return min(get(x * 2, l, mid, fl, fr), get(x * 2 + 1, mid + 1, r, fl, fr)); } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int h, w, n, b; cin >> h >> w >> b >> n; vector<vector<int>> a(n, vector<int>(5)); for(int i = 0; i < n; ++i){ for(int j = 0; j < 5; ++j){ cin >> a[i][j]; } } int ans = 0; if(b){ int low = 0, high = (int)1e6; vector<Data> vc; while(low < high){ int mid = low + high + 1 >> 1; srt.clear(); for(int i = 0; i < n; ++i){ srt.push_back(a[i][1] - mid + 1), srt.push_back(a[i][3] + 1); } srt.push_back(1), srt.push_back(w + 1); srt.push_back(w - mid + 1); sort(srt.begin(), srt.end()); srt.erase(unique(srt.begin(), srt.end()), srt.end()); vector<Data> vc; for(int i = 0; i < n; ++i){ a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1] - mid + 1) - srt.begin(); a[i][3] = lower_bound(srt.begin(), srt.end(), a[i][3] + 1) - srt.begin(); } for(int i = 0; i < n; ++i){ vc.push_back(Data(a[i][0] - mid + 1, a[i][1], a[i][3] - 1, a[i][4])); vc.push_back(Data(a[i][2] + 1, a[i][1], a[i][3] - 1, -a[i][4])); } sort(vc.begin(), vc.end()); int lst = 1, f = 0; Seg tree((int)srt.size() + 4); int up = lower_bound(srt.begin(), srt.end(), w - mid + 1) - srt.begin(); int down = lower_bound(srt.begin(), srt.end(), 1) - srt.begin(); for(auto&i:vc){ if(lst < i.xs && lst >= 1 && lst + mid - 1 <= h){ if(tree.get(1, 0, (int)srt.size() - 2, down, up) <= b){ f = 1; break; } } lst = max(i.xs, 1ll); tree.push(1, 0, (int)srt.size() - 2, i.ys, i.ye, i.v); } if(lst >= 1 && lst + mid - 1 <= h){ if(tree.get(1, 0, (int)srt.size() - 2, down, up) <= b){ f = 1; } } if(f){ low = mid; } else{ high = mid - 1; } for(int i = 0; i < n; ++i){ a[i][1] = srt[a[i][1]] + mid - 1; a[i][3] = srt[a[i][3]] - 1; } } ans = low; } else{ for(int k = 0; k < 2; ++k){ srt.clear(); for(int i = 0; i < n; ++i){ srt.push_back(a[i][1]), srt.push_back(a[i][3] + 1); } srt.push_back(1), srt.push_back(w + 1); sort(srt.begin(), srt.end()); srt.erase(unique(srt.begin(), srt.end()), srt.end()); vector<Data> vc; for(int i = 0; i < n; ++i){ a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1]) - srt.begin(); a[i][3] = lower_bound(srt.begin(), srt.end(), a[i][3] + 1) - srt.begin(); vc.push_back(Data(a[i][0], a[i][1], a[i][3] - 1, 1)); vc.push_back(Data(a[i][2] + 1, a[i][1], a[i][3] - 1, -1)); } vc.push_back(Data(1, 0, (int)srt.size() - 2, 1)); vc.push_back(Data(1, 0, (int)srt.size() - 2, -1)); vc.push_back(Data(h + 1, 0, (int)srt.size() - 2, 1)); vc.push_back(Data(h + 1, 0, (int)srt.size() - 2, -1)); sort(vc.begin(), vc.end()); build(1, 0, (int)srt.size() - 2); int r = 0, mr = -1; for(int l = 0; l < (int)vc.size(); ++l){ if(vc[l].v == -1){ push(1, 0, (int)srt.size() - 2, vc[l].ys, vc[l].ye, -1); } while(r + 1 < (int)vc.size()){ if(tr[1] < vc[r].xs - vc[l].xs){ break; } mr = vc[r].xs; if(tr[1] >= vc[r].xs - vc[l].xs) mr = vc[r].xs; if(vc[r].v == 1) push(1, 0, (int)srt.size() - 2, vc[r].ys, vc[r].ye, 1); ++r; } if(tr[1] >= vc[r].xs - vc[l].xs){ mr = vc[r].xs; } if(r){ ma(ans, mr - vc[l].xs); //cout << vc[l].xs << ' ' << vc[l].ys << ' ' << vc[l].ye << ' ' << vc[l].v << endl; //cout << vc[r - 1].xs << ' ' << vc[r - 1].ys << ' ' << vc[r - 1].ye << ' ' << vc[r - 1].v << endl; } } for(int i = 0; i < n; ++i){ a[i][1] = srt[a[i][1]]; a[i][3] = srt[a[i][3]] - 1; swap(a[i][0], a[i][1]); swap(a[i][2], a[i][3]); } swap(h, w); } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

pyramid_base.cpp: In function 'void build(long long int, long long int, long long int)':
pyramid_base.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int m = s + e >> 1;
      |             ~~^~~
pyramid_base.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int, long long int)':
pyramid_base.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int m = s + e >> 1;
      |             ~~^~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:115:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |             int mid = low + high + 1 >> 1;
      |                       ~~~~~~~~~~~^~~
#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...