| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 725028 |
2023-04-16T13:17:28 Z |
sofija6 |
Wall (IOI14_wall) |
C++14 |
|
1 ms |
212 KB |
#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)
{
if (lazy1[2*x].first==-1 || lazy1[x].first>lazy1[2*x].first || (lazy2[2*x].first!=-1 && lazy2[2*x].second>lazy1[2*x].second && lazy2[2*x].second<lazy1[x].second))
lazy1[2*x]=lazy1[x];
if (lazy1[2*x+1].first==-1 || lazy1[x].first>lazy1[2*x+1].first || (lazy2[2*x+1].first!=-1 && lazy2[2*x+1].second>lazy1[2*x+1].second && lazy2[2*x+1].second<lazy1[x].second))
lazy1[2*x+1]=lazy1[x];
}
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)
{
if (lazy2[2*x].first==-1 || lazy2[x].first<lazy2[2*x].first || (lazy1[2*x].first!=-1 && lazy1[2*x].second>lazy2[2*x].second && lazy1[2*x].second<lazy2[x].second))
lazy2[2*x]=lazy2[x];
if (lazy2[2*x+1].first==-1 || lazy2[x].first<lazy2[2*x+1].first || (lazy1[2*x+1].first!=-1 && lazy1[2*x+1].second>lazy2[2*x+1].second && lazy1[2*x+1].second<lazy2[x].second))
lazy2[2*x+1]=lazy2[x];
}
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);
cout << finalHeight[i] << " ";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
