Submission #479646

#TimeUsernameProblemLanguageResultExecution timeMemory
479646ApiramWall (IOI14_wall)C++14
100 / 100
1077 ms99340 KiB
#include <bits/stdc++.h> #include "wall.h" using namespace std; using ll = long long; using ld = long double; using vl = vector<long long>; #define mp make_pair #define pb push_back #define pp pop_back #define ff first #define ss second #define lb lower_bound #define ub upper_bound #define all(x) (x).begin() , (x).end() const int N = 2*100005; const long long MOD = 1e9+7; const long double EPS = 0.000000001; const double PI = 3.14159265358979323846; const int nx[4]={1, -1, 0, 0}, ny[4]={0, 0, 1, -1}; long long gcd(int a, int b) { return (b==0?a:gcd(b, a%b)); } long long lcm(int a, int b) { return a*(b/gcd(a, b)); } long long fact(int a) { return (a==1?1:a*fact(a-1)); } int up[4*2000005], down[4*2000005]; bitset<4*2000005>add; void prop(int v, int l, int r) { down[v*2]=min(down[v*2], down[v]); down[v*2]=max(down[v*2], up[v]); up[v*2]=max(up[v*2], up[v]); up[v*2]=min(up[v*2], down[v]); down[v*2+1]=min(down[v*2+1], down[v]); down[v*2+1]=max(down[v*2+1], up[v]); up[v*2+1]=max(up[v*2+1], up[v]); up[v*2+1]=min(up[v*2+1], down[v]); } void update0(int v, int l, int r, int lo, int hi, int val, int op) { if(l>hi||r<lo) return; if(l>=lo&&r<=hi) { if(op==1) { up[v]=max(up[v], val); down[v]=max(down[v], val); } else if(op==2) { up[v]=min(up[v], val); down[v]=min(down[v], val); } return; } prop(v, l, r); down[v]=1000000007, up[v]=0; update0(v*2, l, (l+r)/2, lo, hi, val, op); update0(v*2+1, (l+r)/2+1, r, lo, hi, val, op); } int query(int v, int l, int r, int ind) { if(l==r) return up[v]; int mid=(l+r)/2; prop(v, l, r); down[v]=1000000007, up[v]=0; if(ind<=mid) return query(v*2, l, mid, ind); else return query(v*2+1, mid+1, r, ind); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ memset(up, 0, sizeof up); memset(down, 1000000007, sizeof down); for(int l=0;l<k;l++) { int t=op[l], a=left[l], b=right[l], w=height[l]; update0(1, 0, n-1, a, b, w, t); } for(int l=0;l<n;l++) finalHeight[l]=query(1, 0, n-1, l); 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...