Submission #338568

#TimeUsernameProblemLanguageResultExecution timeMemory
338568Sho10Wall (IOI14_wall)C++14
100 / 100
1077 ms69688 KiB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10 #include "wall.h" #define ll long long #define double long double #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define all(a) (a).begin(), (a).end() #define f first #define s second #define pb push_back #define mp make_pair #define pi pair #define rc(s) return cout<<s,0 #define endl '\n' #define mod 1000000007 #define PI 3.14159265359 #define MAXN 100005 #define INF 1000000005 #define LINF 1000000000000000005ll #define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; pair<int,int>tree[8000010]; void build(int node,int l,int r){ if(l==r){ tree[node]=mp(-1,-1); return; } ll mid=(l+r)>>1ll; build(2*node,l,mid); build(2*node+1,mid+1,r); } void add(pair<int,int> &s,pair<int,int> &j){ if(s==mp(-1,-1)){ return; } if(j==mp(-1,-1)){ j=s; s=mp(-1,-1); return; } int hs=s.f,rs=s.s,hj=j.f,rj=j.s; if(rs<hj){ j={max(rs,hs),min(rs,rj)}; }else{ j={max(hj,hs),min(rs,rj)}; } s=mp(-1,-1); return; } void update(int node,int l,int r,int st,int dr,int type,int h){ if(st>dr){ return; } if(l==st&&r==dr){ pair<int,int>p={0,0}; if(type==1){ p.f=h; p.s=100000; }else { p.s=h; } add(p,tree[node]); return; } pair<int,int>p=tree[node]; add(tree[node],tree[node*2]); add(p,tree[node*2+1]); int mid=(l+r)>>1ll; update(2*node,l,mid,st,min(dr,mid),type,h); update(2*node+1,mid+1,r,max(st,mid+1),dr,type,h); return; } int query(int node,int l,int r,int pos){ if(l==r){ return tree[node].f; } pair<int,int>p=tree[node]; add(tree[node],tree[node*2]); add(p,tree[node*2+1]); int mid=(l+r)>>1ll; if(pos<=mid){ return query(2*node,l,mid,pos); }else return query(2*node+1,mid+1,r,pos); } void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){ build(1,1,n); for(int i=0;i<k;i++) { update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]); } for(int i=0;i<n;i++) { finalHeight[i]=query(1,1,n,i+1); } return; } /* int32_t main(){ CODE_START; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...