Submission #261592

#TimeUsernameProblemLanguageResultExecution timeMemory
261592HeheheWall (IOI14_wall)C++14
100 / 100
849 ms77688 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define sz(x) (int)((x).size()) //#define int long long #include "wall.h" const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const int inf = 2e9; const ll mod = 1e9 + 7; const int N = 2e6 + 11; const ll INF64 = 3e18 + 1; const double eps = 1e-14; const double PI = acos(-1); //ifstream in(".in"); //ofstream out(".out"); int mx[4*N], mn[4*N], ans[N]; void build(int v, int l, int r){ mx[v] = 0; mn[v] = inf; if(l == r)return; int mid = (l + r) >> 1; build(2*v, l, mid); build(2*v + 1, mid + 1, r); } void push(int v, int l, int r){ if(l == r)return; int L = 2*v, R = 2*v + 1; mx[L] = min(mx[L],mn[v]); mn[L] = min(mn[L],mn[v]); mn[L] = max(mn[L],mx[v]); mx[L] = max(mx[L],mx[v]); mx[R] = min(mx[R],mn[v]); mn[R] = min(mn[R],mn[v]); mn[R] = max(mn[R],mx[v]); mx[R] = max(mx[R],mx[v]); mn[v] = inf; mx[v] = 0; } void update(int v, int tl, int tr, int l, int r, int H, int type){ //if(tl > r || tr < l)return; push(v, tl, tr); if(l <= tl && tr <= r){ if(type == 1){ mx[v] = max(mx[v], H); mn[v] = max(mn[v], H); }else{ mx[v] = min(mx[v], H); mn[v] = min(mn[v], H); } return; } int mid = (tl + tr) >> 1; if(l <= mid)update(2*v, tl, mid, l, r, H, type); if(r > mid)update(2*v + 1, mid + 1, tr, l, r, H, type); } void WooHoo(int v, int l, int r){ push(v, l, r); if(l == r){ ans[l] = mx[v]; return; } int mid = (l + r) >> 1; WooHoo(2*v, l, mid); WooHoo(2*v + 1, mid + 1, r); } void buildWall (int n, int k, int op[], int left[], int right[], int h[], int finalHeight[]){ build(1, 1, n); for(int i = 0; i < k; i++){ update(1, 1, n, left[i] + 1, right[i] + 1, h[i], op[i]); } WooHoo(1, 1, n); for(int i = 0; i < n; i++)finalHeight[i] = ans[i + 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...