Submission #147263

#TimeUsernameProblemLanguageResultExecution timeMemory
147263karmaWall (IOI14_wall)C++11
0 / 100
702 ms13472 KiB
#include<bits/stdc++.h> using namespace std; const int N = int(2e6) + 7; const int oo = int(1e9) + 7; struct TSegment{ int n, low, high, val; vector<int> st, l, h; TSegment(int n = 0): n(n) { st.resize(n << 2 | 1), l.resize(n << 2 | 1), h.resize(n << 2 | 1); } void Build(int x, int low, int high) { l[x] = low, h[x] = high, st[x] = 0; if(l[x] == h[x]) return; int mid = (low + high) >> 1; Build(x << 1, low, mid); Build(x << 1 | 1, mid + 1, high); } void Down(int x) { if(l[x] == h[x] && st[x] == oo) {st[x] = 0; return;} if(l[x] == h[x] || st[x] == -oo) return; if(st[x] == oo) { st[x << 1] = st[x << 1 | 1] = oo; return; } if(1ll * st[x << 1] * st[x] < 0) st[x << 1] = st[x]; else st[x << 1] = max(st[x], st[x << 1]); if(1ll * st[x << 1 | 1] * st[x] < 0) st[x << 1 | 1] = st[x]; else st[x << 1 | 1] = max(st[x], st[x << 1 | 1]); st[x] = -oo; } void Update(int x) { Down(x); if(l[x] > high || h[x] < low) return; if(l[x] >= low && h[x] <= high) { if(val == oo) st[x] = oo; else if(1ll * st[x] * val < 0) st[x] = val; else st[x] = max(st[x], val); Down(x); return; } Update(x << 1); Update(x << 1 | 1); } void Update(int l, int h, int v) { low = l, high = h, val = v; Update(1); } int Query(int x, int pos) { Down(x); if(l[x] > pos || h[x] < pos) return -oo; if(l[x] == pos && h[x] == pos) return st[x]; return max(Query(x << 1, pos), Query(x << 1 | 1, pos)); } } Irene; void buildWall(int n, int k, int op[], int lef[], int rig[], int h[], int ans[]) { Irene = TSegment(n); Irene.Build(1, 0, n - 1); for(int i = 0; i < k; ++i) { if(op[i] == 1) { if(h[i]) Irene.Update(lef[i], rig[i], h[i]); }else { if(h[i] == 0) Irene.Update(lef[i], rig[i], oo); else Irene.Update(lef[i], rig[i], -h[i]); } } for(int i = 0; i < n; ++i) ans[i] = abs(Irene.Query(1, i)); } //int _n, _k, _op[N], _lef[N], _rig[N], _h[N], ans[N]; // //int main() //{ // ios_base::sync_with_stdio(0); // cin.tie(0),cout.tie(0); // if(fopen("test.inp", "r")) { // freopen("test.inp", "r", stdin); // freopen("test.out", "w", stdout); // } // cin >> _n >> _k; // for(int i = 0; i < _k; ++i) cin >> _op[i] >> _lef[i] >> _rig[i] >> _h[i]; // buildWall(_n, _k, _op, _lef, _rig, _h, ans); // for(int i = 0; i < _n; ++i) cout << ans[i] << ' '; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...