| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 667799 | Baytoro | 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 ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define int long long
#define endl '\n'
void fopn(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
const int INF=1e12,mod=1e9+7;
const int N=1e5+5;
struct op{
int t,l,r,v;
} oper[N];
pair<int,int> st[4*N];
int ans[N];
pair<int,int> f(pair<int,int> a, pair<int,int> b){
if(a.sc<b.fr)
return {a.sc,a.sc};
if(a.fr>b.sc)
return {a.fr,a.fr};
return {max(a.fr,b.fr),min(a.sc,b.sc)};
}
void push(int x){
if(st[x]!=make_pair(-INF,INF)){
st[2*x]=f(st[x],st[2*x]);
st[2*x+1]=f(st[x],st[2*x+1]);
st[x]={-INF,INF};
}
}
void update(int x, int l, int r, int lx, int rx, pair<int,int> v){
if(l>rx || r<lx) return;
if(lx<=l && r<=rx){
st[x]=f(v,st[x]);
return;
}
if(l!=r) push(x);
int md=(l+r)/2;
update(2*x,l,md,lx,rx,v);
update(2*x+1,md+1,r,lx,rx,v);
}
void get(int x, int l, int r){
if(l==r){
ans[l]=st[x].fr;
return;
}
push(x);
int md=(l+r)/2;
get(2*x,l,md);
get(2*x+1,md+1,r);
}
int n,k;
void init(int x=1, int l=0, int r=n-1){
if(l==0 && r==n-1)
st[x]={0,0};
else
st[x]={-INF,INF};
if(l==r) return;
int md=(l+r)/2;
init(2*x,l,md);
init(2*x+1,md+1,r);
}
void build(){
init();
for(int i=0;i<k;i++){
pair<int,int> a={-INF,INF};
if(oper[i].t==1)
a.fr=oper[i].v;
else
a.sc=oper[i].v;
update(1,0,n-1,oper[i].l,oper[i].r,a);
}
get(1,0,n-1);
}
void solve(){
cin>>n>>k;
for(int i=0;i<k;i++){
cin>>oper[i].t>>oper[i].l>>oper[i].r>>oper[i].v;
}
build();
for(int i=0;i<n;i++)
cout<<ans[i]<<'\n';
}
main(){
//fopn("intersec1");
ios;
int T=1;
// cin>>T;
while(T--){
solve();
}
}