제출 #834881

#제출 시각아이디문제언어결과실행 시간메모리
834881sadsa벽 (IOI14_wall)C++17
24 / 100
708 ms84364 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using ii = pair<int, int>; using vii = vector<ii>; using i64 = int64_t; using vl = vector<i64>; using ll = pair<i64, i64>; using vll = vector<ll>; constexpr int iINF = numeric_limits<int>::max(); constexpr i64 lINF = numeric_limits<i64>::max(); #define RANGE(x) begin(x), end(x) template <typename... T> void DBG(T&&... args) { //((cerr << args << ' '), ...) << '\n'; } template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) { out << '{'; for (size_t i = 0; i < vec.size()-1; ++i) out << vec[i] << ", "; out << vec.back() << '}'; return out; } template <typename T1, typename T2> ostream &operator<<(ostream &out, const pair<T1, T2> &pr) { out << '(' << pr.first << ", " << pr.second << ')'; return out; } struct Node { int mi{}, ma{}; int ladd = -1; int lrem = -1; void cpy(const Node &n) { if (ladd == -1) ladd = n.ladd; else if (n.ladd != -1) ladd = max(ladd, n.ladd); if (lrem == -1) lrem = n.lrem; else if (n.lrem != -1) lrem = min(lrem, n.lrem); } void prop() { if (ladd!=-1) { if (ladd > mi) mi = ladd; if (ladd > ma) ma = ladd; } if (lrem!=-1) { if (lrem < ma) ma = lrem; if (lrem < mi) mi = lrem; } //tie(mi, ma) = minmax(mi, ma); } void reset() { ladd = -1; lrem = -1; } }; static constexpr int N = 1 << 21; struct Seg { vector<Node> seg = vector<Node>(N * 2); void prop(int p) { seg[p].prop(); if (p < N) { seg[p*2].cpy(seg[p]); seg[p*2+1].cpy(seg[p]); } if (seg[p].ladd != -1) DBG("PROP ADD", p, seg[p].ladd); if (seg[p].lrem != -1) DBG("PROP REM", p, seg[p].lrem); seg[p].reset(); } void update(int l, int r, int ladd, int lrem, int vl=0, int vr=N-1, int p=1) { prop(p); if (l > vr || r < vl) return; DBG(l, r, vl, vr, p, ladd, lrem); if (l <= vl && vr <= r) { seg[p].lrem = lrem; seg[p].ladd = ladd; DBG("endnode"); return; } int mid = (vl+vr)/2; update(l, r, ladd, lrem, vl, mid, p*2); update(l, r, ladd, lrem, mid+1, vr, p*2+1); } void prop_rec(int p=1) { prop(p); if (p < N) { prop_rec(p*2); prop_rec(p*2+1); } else { prop(p); } } }; void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ Seg seg; seg.prop_rec(); DBG("START"); for (int i = 0; i < k; ++i) { DBG("-----------UPDATE", i); seg.update(left[i], right[i], op[i] == 1? height[i]: -1, op[i] == 2? height[i]: -1); } DBG("DONE"); seg.prop_rec(); for (int i = 0; i < n; ++i) finalHeight[i] = seg.seg[i + N].mi; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...