Submission #1125083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125083		KhoaDuy	Wall (IOI14_wall)	C++20	100 / 100	597 ms	48904 KiB

wall

#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(0,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;
    }
}*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39