Submission #1196384

#TimeUsernameProblemLanguageResultExecution timeMemory
1196384AMel0nWall (IOI14_wall)C++20
0 / 100
110 ms8008 KiB
#include "wall.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,N) for(ll i = 0; i < N; i++) #define all(x) (x).begin(), (x).end() #define F first #define S second const int INF = 1e9+7; int N; vector<int> tree; vector<pair<int,int>> lazy; void pushdown(int tl, int tr, int i) { if (lazy[i].F != -INF) { if (tree[i] < lazy[i].F && lazy[i].S == 1) tree[i] = lazy[i].F; // add if (tree[i] > lazy[i].F && lazy[i].S == 2) tree[i] = lazy[i].F; // remove if (tl != tr) { lazy[i*2] = lazy[i]; lazy[i*2+1] = lazy[i]; } lazy[i] = {-INF,-INF}; } } void update(pair<int,int> v, int l, int r, int tl = 0, int tr = N-1, int i = 1) { pushdown(tl, tr, i); if (l > r) return; if (tl == l && tr == r) { lazy[i] = v; pushdown(tl, tr, i); return; } int tm = (tl + tr) / 2; update(v, l, min(r, tm), tl, tm, i * 2); update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1); } int query(int p, int tl = 0, int tr = N-1, int i = 1) { pushdown(tl, tr, i); if (tl == tr) return tree[i]; int tm = (tl + tr) / 2; if (p <= tm) return query(p, tl, tm, i * 2); else return query(p, tm + 1, tr, i * 2 + 1); } void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) { ::N = N; tree.resize(4*N); lazy.resize(4*N, {-INF, -INF}); for(int i = 0; i < K; i++) { update({height[i], op[i]}, left[i], right[i]); } for(int i = 0; i < N; i++) { finalHeight[i] = 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...