| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125082 | KhoaDuy | Wall (IOI14_wall) | C++20 | 0 ms | 0 KiB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
struct U{
int Max=-1e9,Min=1e9;
};
U UU(U &app,U &node){
U pa;
pa.Max=node.Max;
pa.Min=node.Min;
pa.Max=max(pa.Max,app.Max);
pa.Min=max(pa.Min,app.Max);
pa.Min=min(pa.Min,app.Min);
return pa;
}
U Uid;
struct segtree{
vector<U> d;
int n,lg;
void build(int siz){
n=1;
while(n<siz){
n<<=1;
}
d.assign(n<<1,Uid);
lg=__lg(n);
}
void apply(int v,U &f){
d[v]=UU(f,d[v]);
}
void push(int v){
apply(v<<1,d[v]);
apply((v<<1)|1,d[v]);
d[v]=Uid;
}
void update(int l,int r,U &f){
if(l>=r){
return;
}
l+=n,r+=n;
for(int i=lg;i>=1;i--){
if((l>>i<<i)!=l){
push(l>>i);
}
if((r>>i<<i)!=r){
push(r>>i);
}
}
for(;l<r;l>>=1,r>>=1){
if(l&1){
apply(l,f);
l++;
}
if(r&1){
r--;
apply(r,f);
}
}
}
int query(int l){
l+=n;
for(int i=lg;i>=1;i--){
push(l>>i);
}
return (min(max(0LL,d[l].Max),d[l].Min));
}
};
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
segtree seg;
seg.build(n);
for(int i=0;i<k;i++){
U f;
if(op[i]==1){
f.Max=height[i];
}
if(op[i]==2){
f.Min=height[i];
}
seg.update(left[i],right[i]+1,f);
}
for(int i=0;i<n;i++){
finalHeight[i]=seg.query(i);
}
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,k;
cin >> n >> k;
int op[k],left[k],right[k],height[k],finalHeight[n];
for(int i=0;i<k;i++){
cin >> op[i] >> left[i] >> right[i] >> height[i];
}
buildWall(n,k,op,left,right,height,finalHeight);
for(int i=0;i<n;i++){
cout << finalHeight[i] << endl;
}
}*/