| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 725026 |
2023-04-16T13:13:37 Z |
sofija6 |
Wall (IOI14_wall) |
C++14 |
|
760 ms |
15312 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[x].first!=-1 && 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[x].first!=-1 && 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[x].first!=-1 && 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[x].first!=-1 && 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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
122 ms |
8124 KB |
Output is correct |
| 3 |
Correct |
265 ms |
5152 KB |
Output is correct |
| 4 |
Correct |
760 ms |
14792 KB |
Output is correct |
| 5 |
Correct |
304 ms |
15308 KB |
Output is correct |
| 6 |
Correct |
297 ms |
15312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
