Submission #1192579

#TimeUsernameProblemLanguageResultExecution timeMemory
1192579lrnnzWall (IOI14_wall)C++17
100 / 100
668 ms214344 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #include <cmath> #include "wall.h" using namespace std; #define all(a) (a).begin(), (a).end() #define sz(a) (int)(a).size() #define pb push_back #define ll long long #define ld long double #define ui uint64_t #define ar array #define us unordered_set #define cont(set, element) ((set).find(element) != (set).end()) /********* DEBUG *********/ template <typename T> void outvec(const vector<T>& Z){ for (const T& x : Z) cout << x << ' '; cout << "\n"; } void printVariable(const any& var) { if (!var.has_value()) { cout << "null"; return; } if (var.type() == typeid(int)) { cout << any_cast<int>(var); } else if (var.type() == typeid(double)) { cout << any_cast<double>(var); } else if (var.type() == typeid(float)) { cout << any_cast<float>(var); } else if (var.type() == typeid(char)) { cout << any_cast<char>(var); } else if (var.type() == typeid(bool)) { cout << (any_cast<bool>(var) ? "true" : "false"); } else if (var.type() == typeid(string)) { cout << any_cast<string>(var); } else if (var.type() == typeid(const char*)) { cout << any_cast<const char*>(var); } else if (var.type() == typeid(long long)) { cout << any_cast<long long>(var); } else { cout << "[unknown type]"; } } template<typename... Args> void outval(Args... args) { vector<any> variables = {args...}; for (size_t i = 0; i < variables.size(); ++i) { printVariable(variables[i]); if (i != variables.size() - 1) { cout << " "; } } cout << "\n"; } #define nl "\n" #define sp << " " << /********* DEBUG *********/ const ll MOD = 1000000007; const ll MOD2 = 998244353; const ll MOD3 = 1000000000; const ll needMOD = 987654321; const ll mxN = 2000001; const ll inf = 1e18; struct nd { ll minv=0,maxv=0,lazy=-1; }; vector<nd> tree(8000009); void push(ll node, ll start, ll end){ if (tree[node].lazy == -1) return; tree[node].minv = tree[node].lazy; tree[node].maxv = tree[node].lazy; if (start != end){ tree[2*node+1].lazy = tree[node].lazy; tree[2*node+2].lazy = tree[node].lazy; } tree[node].lazy = -1; } void updMax(ll l, ll r, ll val, ll node, ll start, ll end){ push(node, start, end); if (l > end || r < start) return; if (tree[node].minv >= val) return; if (l <= start && end <= r){ if (tree[node].maxv < val){ tree[node].lazy = val; push(node, start, end); return; } } if (start == end) return; ll m = (start + end) / 2; updMax(l,r,val,2*node+1,start,m); updMax(l,r,val,2*node+2,m+1,end); tree[node].minv = min(tree[2*node+1].minv, tree[2*node+2].minv); tree[node].maxv = max(tree[2*node+1].maxv, tree[2*node+2].maxv); } void updMin(ll l, ll r, ll val, ll node, ll start, ll end){ push(node, start, end); if (l > end || r < start) return; if (tree[node].maxv <= val) return; if (l <= start && end <= r){ if (tree[node].minv > val){ tree[node].lazy = val; push(node, start, end); return; } } if (start == end) return; ll m = (start + end) / 2; updMin(l,r,val,2*node+1,start,m); updMin(l,r,val,2*node+2,m+1,end); tree[node].minv = min(tree[2*node+1].minv, tree[2*node+2].minv); tree[node].maxv = max(tree[2*node+1].maxv, tree[2*node+2].maxv); } nd quer(ll idx, ll node, ll start, ll end){ push(node, start, end); if (start == end && idx == end) return tree[node]; ll m = (start + end) / 2; if (idx <= m) return quer(idx, 2 * node + 1, start, m); else return quer(idx, 2 * node + 2, m + 1, end); return {0}; } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ for (int i = 0; i < k; i++){ if (op[i] == 1) updMax(left[i], right[i], height[i], 0, 0, n-1); else updMin(left[i], right[i], height[i], 0, 0, n-1); } for (int i = 0; i < n; i++){ finalHeight[i] = quer(i, 0, 0, n-1).minv; } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...