| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 288150 | Theo830 | Wall (IOI14_wall) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define f(i,a,b) for(ll i = a;i <b;i++)
#define ii pair<ll,bool>
#define S second
#define F first
struct node{
ll maxi = 0,mini = 1e9+7;
vector<ii>up;
};
vector<node> seg(8000000);
void vale(vector<ii> &up,bool d,ll h){
if(up.empty() || up.back().S != d){
if(!up.empty()){
up.erase(up.begin());
}
up.push_back(ii(h,d));
}
else{
if(d){
up.back().F = max(up.back().F,h);
}
else{
up.back().F = min(up.back().F,h);
}
}
assert(up.size() <= 2);
}
void upd(ll idx,ll s,ll e,ll qs,ll qe,bool d,ll h){
if(qs <= s && e <= qe){
vale(seg[idx].up,d,h);
if(d){
seg[idx].maxi = max(h,seg[idx].maxi);
seg[idx].mini = max(h,seg[idx].mini);
}
else{
seg[idx].maxi = min(h,seg[idx].maxi);
seg[idx].mini = min(h,seg[idx].mini);
}
return;
}
if(qs > e || s > qe){
return;
}
ll mid = (s+e)/2;
for(auto x:seg[idx].up){
vale(seg[idx*2].up,x.S,x.F);
vale(seg[idx*2+1].up,x.S,x.F);
if(x.S){
seg[idx*2].maxi = max(x.F,seg[idx*2].maxi);
seg[idx*2].mini = max(x.F,seg[idx*2].mini);
}
else{
seg[idx*2].maxi = min(x.F,seg[idx*2].maxi);
seg[idx*2].mini = min(x.F,seg[idx*2].mini);
}
if(x.S){
seg[idx*2+1].maxi = max(x.F,seg[idx*2+1].maxi);
seg[idx*2+1].mini = max(x.F,seg[idx*2+1].mini);
}
else{
seg[idx*2+1].maxi = min(x.F,seg[idx*2+1].maxi);
seg[idx*2+1].mini = min(x.F,seg[idx*2+1].mini);
}
}
seg[idx].up.clear();
upd(idx*2,s,mid,qs,qe,d,h);
upd(idx*2+1,mid+1,e,qs,qe,d,h);
seg[idx].maxi = max(seg[idx*2].maxi,seg[idx*2+1].maxi);
seg[idx].mini = min(seg[idx*2].mini,seg[idx*2+1].mini);
}
node query(ll idx,ll s,ll e,ll qs,ll qe){
if(qs <= s && e <= qe){
return seg[idx];
}
if(qs > e || s > qe){
node x;
return x;
}
ll mid = (s+e)/2;
for(auto x:seg[idx].up){
vale(seg[idx*2].up,x.S,x.F);
vale(seg[idx*2+1].up,x.S,x.F);
if(x.S){
seg[idx*2].maxi = max(x.F,seg[idx*2].maxi);
seg[idx*2].mini = max(x.F,seg[idx*2].mini);
}
else{
seg[idx*2].maxi = min(x.F,seg[idx*2].maxi);
seg[idx*2].mini = min(x.F,seg[idx*2].mini);
}
if(x.S){
seg[idx*2+1].maxi = max(x.F,seg[idx*2+1].maxi);
seg[idx*2+1].mini = max(x.F,seg[idx*2+1].mini);
}
else{
seg[idx*2+1].maxi = min(x.F,seg[idx*2+1].maxi);
seg[idx*2+1].mini = min(x.F,seg[idx*2+1].mini);
}
}
seg[idx].up.clear();
node a = query(idx*2,s,mid,qs,qe);
node b = query(idx*2+1,mid+1,e,qs,qe);
node c;
c.maxi = max(a.maxi,b.maxi);
c.mini = min(a.mini,b.mini);
return c;
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,k;
cin>>n>>k;
while(k--){
ll t,l,r,h;
cin>>t>>l>>r>>h;
l++,r++;
upd(1,1,n,l,r,t == 1,h);
}
f(i,0,n){
cout<<query(1,1,n,i+1,i+1).maxi<<" ";
}
}