Submission #1092847

#TimeUsernameProblemLanguageResultExecution timeMemory
1092847davieduWall (IOI14_wall)C++17
8 / 100
3072 ms14052 KiB
#include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(0); cin.tie(0) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) (int) (a).size() #define ll long long #define ld long double #define pb push_back struct P{ ll x, y; }; void dbg_out() { cerr << endl; } template <typename H, typename... T> void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); } #define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); } #define bound array<int, 2> const bound neutral = {0, INT_MAX}; const bound no_lazy = {-1, -1}; const int MI = 0, MA = INT_MAX; class Segtree{ public: int n; vector<int> t, hi, lo; // lazy is not a bound, but an operation with 2 parameters Segtree(int size){ n = 1; while (n < size) n <<= 1; t.resize(2*n); hi.resize(2*n, MI); lo.resize(2*n, MA); } void apply(int i){ t[i] = max(t[i], hi[i]); t[i] = min(t[i], lo[i]); hi[i] = MI; lo[i] = MA; } void prop(int i){ if (lo[i] == MA && hi[i] == MI) return; if (i >= n) apply(i); else{ prop(2*i); prop(2*i+1); lo[2*i] = lo[2*i+1] = lo[i]; hi[2*i] = hi[2*i+1] = hi[i]; hi[i] = MI; lo[i] = MA; } } void update(int l, int r, int i, int a, int b, int v, int op){ prop(i); if (b < l || r < a) return; if (a <= l && r <= b){ if (op == 1) hi[i] = v; else lo[i] = v; prop(i); return; } int m = (l+r)/2; update(l, m, 2*i, a, b, v, op); update(m+1, r, 2*i+1, a, b, v, op); } void update(int l, int r, int v, int op){ update(0, n-1, 1, l, r, v, op); } int query(int l, int r, int i, int pos){ prop(i); if (l == r && l == pos) return t[i]; int m = (l+r)/2; if (pos <= m) return query(l, m, 2*i, pos); else return query(m+1, r, 2*i+1, pos); } int query(int pos){ return query(0, n-1, 1, pos); } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ Segtree seg (n); for (int i=0; i<k; i++){ seg.update(left[i], right[i], height[i], op[i]); } for (int i=0; i<n; i++){ finalHeight[i] = seg.query(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...