Submission #725010

#TimeUsernameProblemLanguageResultExecution timeMemory
725010sofija6Wall (IOI14_wall)C++14
24 / 100
757 ms15328 KiB
#include <bits/stdc++.h> #define ll int using namespace std; ll s; struct element { ll minn=0,maxx=0; }; struct seg_tree { vector<element> st; vector<pair<ll,ll> > lazy1,lazy2; void Init(ll n) { s=1; while (s<n) s <<= 1; st.resize(2*s+2); lazy1.resize(2*s+2,{-1,-1}); lazy2.resize(2*s+2,{-1,-1}); } void Propagate_1(ll x,ll lx,ll rx) { if (lazy1[x].first==-1) return; st[x].minn=max(st[x].minn,lazy1[x].first); st[x].maxx=max(st[x].maxx,lazy1[x].first); if (x<s) { lazy1[2*x].first=lazy1[2*x].first==-1?lazy1[x].first : max(lazy1[2*x].first,lazy1[x].first); lazy1[2*x+1].first=lazy1[2*x+1].first==-1?lazy1[x].first : max(lazy1[2*x+1].first,lazy1[x].first); } lazy1[x]={-1,-1}; } void Propagate_2(ll x,ll lx,ll rx) { if (lazy2[x].first==-1) return; st[x].minn=min(st[x].minn,lazy2[x].first); st[x].maxx=min(st[x].maxx,lazy2[x].first); if (x<s) { lazy2[2*x].first=lazy2[2*x].first==-1?lazy2[x].first : min(lazy2[2*x].first,lazy2[x].first); lazy2[2*x+1].first=lazy2[2*x+1].first==-1?lazy2[x].first : min(lazy2[2*x+1].first,lazy2[x].first); } lazy2[x]={-1,-1}; } void Add(ll l,ll r,pair<ll,pair<ll,ll> > val,ll x,ll lx,ll rx) { if (lazy2[x].second==-1 || lazy1[x].second<lazy2[x].second) { Propagate_1(x,lx,rx); Propagate_2(x,lx,rx); } else { Propagate_2(x,lx,rx); Propagate_1(x,lx,rx); } if (lx>r || rx<l) return; if (lx>=l && rx<=r) { if (val.first==1) lazy1[x]=val.second; else lazy2[x]=val.second; Propagate_1(x,lx,rx); Propagate_2(x,lx,rx); return; } ll mid=(lx+rx)/2; Add(l,r,val,2*x,lx,mid); Add(l,r,val,2*x+1,mid+1,rx); st[x]={min(st[2*x].minn,st[2*x+1].minn),max(st[2*x].maxx,st[2*x+1].maxx)}; } ll Calc(ll pos,ll x,ll lx,ll rx) { if (lazy2[x].second==-1 || lazy1[x].second<lazy2[x].second) { Propagate_1(x,lx,rx); Propagate_2(x,lx,rx); } else { Propagate_2(x,lx,rx); Propagate_1(x,lx,rx); } if (st[x].minn==st[x].maxx) return st[x].minn; ll mid=(lx+rx)/2; if (pos<=mid) return Calc(pos,2*x,lx,mid); return Calc(pos,2*x+1,mid+1,rx); } }; seg_tree S; void buildWall(ll n,ll k,ll op[],ll left[],ll right[],ll height[],ll finalHeight[]) { S.Init(n); for (ll i=0;i<k;i++) S.Add(left[i]+1,right[i]+1,{op[i],{height[i],i}},1,1,s); for (ll i=0;i<n;i++) finalHeight[i]=S.Calc(i+1,1,1,s); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...