제출 #1014175

#제출 시각아이디문제언어결과실행 시간메모리
1014175AmirAli_H1벽 (IOI14_wall)C++17
100 / 100
726 ms102416 KiB
// In the name of Allah #include <bits/stdc++.h> #include "wall.h" using namespace std; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef complex<ld> cld; #define all(x) (x).begin(),(x).end() #define len(x) ((ll) (x).size()) #define F first #define S second #define pb push_back #define sep ' ' #define endl '\n' #define Mp make_pair #define kill(x) cout << x << '\n', exit(0) #define set_dec(x) cout << fixed << setprecision(x); #define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll oo = 1e18 + 4; const int maxn = (1 << 21) + 4; int n, q; pll t[2 * maxn]; void upd_lazy(int v, pll x) { if (max(t[v].F, x.F) <= min(t[v].S, x.S)) { t[v].F = max(t[v].F, x.F); t[v].S = min(t[v].S, x.S); } else { if (t[v].S < x.F) t[v] = Mp(x.F, x.F); else t[v] = Mp(x.S, x.S); } } void shift(int v) { pll x = t[v]; t[v] = Mp(-oo, oo); if (x == Mp(-oo, oo)) return ; for (int u : {2 * v + 1, 2 * v + 2}) { upd_lazy(u, x); } } void build(int v, int tl, int tr) { t[v] = Mp(-oo, oo); if (tr - tl == 1) return ; int mid = (tl + tr) / 2; build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr); } void upd_val(int v, int tl, int tr, int l, int r, pll x) { l = max(l, tl); r = min(r, tr); if (l >= tr || r <= tl) return ; if (l == tl && r == tr) { upd_lazy(v, x); return ; } shift(v); int mid = (tl + tr) / 2; upd_val(2 * v + 1, tl, mid, l, r, x); upd_val(2 * v + 2, mid, tr, l, r, x); } ll get_val(int v, int tl, int tr, int i) { if (tr - tl == 1) { ll x = 0; x = max(x, t[v].F); x = min(x, t[v].S); return x; } shift(v); int mid = (tl + tr) / 2; if (i < mid) return get_val(2 * v + 1, tl, mid, i); else return get_val(2 * v + 2, mid, tr, i); } void buildWall(int Nx, int Qx, int op[], int lq[], int rq[], int hq[], int ans[]) { n = Nx; q = Qx; build(0, 0, n); for (int i = 0; i < q; i++) { rq[i]++; if (op[i] == 1) { upd_val(0, 0, n, lq[i], rq[i], Mp(hq[i], oo)); } else { upd_val(0, 0, n, lq[i], rq[i], Mp(-oo, hq[i])); } } for (int i = 0; i < n; i++) ans[i] = get_val(0, 0, n, 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...