Submission #1147320

#TimeUsernameProblemLanguageResultExecution timeMemory
1147320brianhdzmdoWall (IOI14_wall)C++20
0 / 100
117 ms8264 KiB
#include <algorithm> #include <cmath> #include <iostream> #include <math.h> #include <numeric> #include <set> #include <map> #include <string> #include <utility> #include <vector> #include <climits> #define all(a) (a).begin(), (a).end() #define allr(a) (a).rbegin(), (a).rend() #define ll long long #define fr(i, a, b) for (ll i = a; i < b; i++) #define fr1(i, a, b) for (ll i = a - 1; i >= b; i--) #define fi first #define se second #define mp(j, k) make_pair(j, k) #define pb(x) push_back(x) #define pbp(x, y) push_back({x, y}) #define in(x) insert(x) #define vec vector<ll> #define vecv vector<vector<ll> > #define veb vector<bool> #define vecp vector<pair<ll,ll>> #define yes cout << "YES\n"; #define no cout << "NO\n"; #define ac 1e-7 #define fauto(a) \ for (auto i : a) \ cout << i << " "; #define fautop(a) \ for (auto i : a) \ cout << i.fi << " " << i.se << endl; using namespace std; const int N = 2e6 + 5; int ST[4 * N]; int lazyMax[4 * N], lazyMin[4 * N]; void init() { fill(ST, ST + 4 * N, 0); fill(lazyMax, lazyMax + 4 * N, -1); fill(lazyMin, lazyMin + 4 * N, 1e9); } void propagate(int node, int l, int r) { if(lazyMax[node] != -1) //máximo { ST[node] = max(lazyMax[node], ST[node]); if(l != r) { int left = node * 2 + 1; int right = node * 2 + 2; lazyMax[left] = lazyMax[node]; lazyMax[right] = lazyMax[node]; } lazyMax[node] = -1; } if(lazyMin[node] != 1e9) { ST[node] = min(lazyMin[node], ST[node]); if(l != r) { int left = node * 2 + 1; int right = node * 2 + 2; lazyMin[left] = lazyMin[node]; lazyMin[right] = lazyMin[node]; } lazyMin[node] = 1e9; } } void updateMax(int node, int l, int r, int a, int b, int h) { propagate(node, l, r); if(l > b || r < a) return; if(a <= l && r <= b) { lazyMax[node] = max(lazyMax[node], h); propagate(node, l, r); return; } int mid = (l + r) / 2; int left = node * 2 + 1; int right = node * 2 + 2; updateMax(left, l, mid, a, b, h); updateMax(right, mid + 1, r, a, b, h); ST[node] = max(ST[left], ST[right]); } void updateMin(int node, int l, int r, int a, int b, int h) { propagate(node, l, r); if(l > b || r < a) return; if(a <= l && r <= b) { lazyMin[node] = min(lazyMin[node], h); propagate(node, l, r); return; } int mid = (l + r) / 2; int left = node * 2 + 1; int right = node * 2 + 2; updateMin(left, l, mid, a, b, h); updateMin(right, mid + 1, r, a, b, h); ST[node] = min(ST[left], ST[right]); } int query(int node, int l, int r, int pos) { propagate(node, l, r); if(l == r) return ST[node]; int mid = (l + r) / 2; int left = node * 2 + 1; int right = node * 2 + 2; if(pos <= mid) return query(left, l, mid, pos); else return query(right, mid + 1, r, pos); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) { fr(i, 0, k) { int ax = op[i]; int a = left[i]; int b = right[i]; int h = height[i]; if(ax == 1) { updateMax(0, 0, n - 1, a, b, h); } else updateMin(0, 0, n - 1, a, b, h); } fr(i, 0, n) finalHeight[i] = query(0, 0, n - 1, 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...