| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 855877 | vipboy0402hcm | 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<iostream>
#include<vector>
#include<cmath>
#include<stdio.h>
#include<numeric>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
struct lazy{
ll height;
ll type;
ll query;
};
lazy ar[8000017];
vector<ii> res;
ll n,m,u,v,q,k,t;
/*void build(int id,int l,int r){
if(l==r){
ar[id]=0x3f3f3f3f;
return;
}
int m=(l+r)/2;
build(2*id,l,m);
build(2*id+1,m+1,r);
ar[id]=min(ar[2*id],ar[2*id+1]);
}
void apply(ll& a,lazy b,int len){
if(b.a==0&&b.d==0){
return;
}
else{
a=b.assign*len;
a+=b.add*len;
}
}*/
void apply(lazy& a,lazy b){
if(b.type==0){
return;
}
else if(b.type==1){
a.height=max(a.height,b.query);
a.query=b.query;
a.type=b.type;
}
else{
a.height=min(a.height,b.query);
a.query=b.query;
a.type=b.type;
}
}
void propagate(int id,int l,int r){
if(l==r){
return;
}
apply(ar[2*id],ar[id]);
apply(ar[2*id+1],ar[id]);
}
void print(int id,int l,int r){
if(l==r){
cout<<ar[id].height<<"\n";
return;
}
int m=(l+r)/2;
print(2*id,l,m);
print(2*id+1,m+1,r);
}
void propagateAll(int id,int l,int r){
propagate(id,l,r);
ar[id]={ar[id].height,0,0};
if(l==r){
return;
}
int m=(l+r)/2;
propagateAll(2*id,l,m);
propagateAll(2*id+1,m+1,r);
}
void add(int id,int lx,int rx,int l,int r,ll t,ll a){
propagate(id,lx,rx);
ar[id]={ar[id].height,0,0};
if(rx<l||lx>r){
return;
}
if(lx>=l&&rx<=r){
ar[id].height=t==1 ? max(ar[id].height,a) : min(ar[id].height,a);
ar[id].query=a;
ar[id].type=t;
propagate(id,lx,rx);
ar[id]={ar[id].height,0,0};
return;
}
int m=(lx+rx)/2;
add(2*id,lx,m,l,r,t,a);
add(2*id+1,m+1,rx,l,r,t,a);
}
/*segment get(int id,int lx,int rx,int l,int r){
apply(res[id],ar[id],rx-lx+1);
propagate(id,lx,rx);
ar[id]=0;
if(rx<l||lx>r){
return {0,0,0,0};
}
else if(lx>=l&&rx<=r){
return res[id];
}
int m=(lx+rx)/2;
segment a=get(2*id,lx,m,l,r);
segment b=get(2*id+1,m+1,rx,l,r);
return merge(a,b);
}
int find(int id,int l,int r,ll k,ll index){
if(ar[id]!=0){
res[id]+=ar[id];
if(r!=l){
ar[2*id]+=ar[id];
ar[2*id+1]+=ar[id];
}
ar[id]=0;
}
if(index>r){
return -1;
}
if(k>res[id]){
return -1;
}
if(l==r){
return l;
}
int m=(l+r)/2;
int res=find(2*id,l,m,k,index);
if(res==-1){
res=find(2*id+1,m+1,r,k,index);
}
return res;
}*/
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
while(m--){
cin>>k>>u>>v>>q;
add(1,0,n-1,u,v,k,q);
}
propagateAll(1,0,n-1);
print(1,0,n-1);
return 0;
}