Submission #883734

#	Time	Username	Problem	Language	Result	Execution time	Memory
883734		andro	Wall (IOI14_wall)	C++14	32 / 100	330 ms	63348 KiB

wall

#include <bits/stdc++.h>
using namespace std;
int O=0;
const int N=2e6+5;
struct segtree{
    int t[4*N]={(int)-1e9};
    map<pair<int,int>,int>M;
    void build(int v,int tl,int tr){
        M[{tl,tr}]=v;
        if(tl==tr){

        }
        else {
            int tm=(tl+tr)/2;
            build(v*2,tl,tm);
            build(v*2+1,tm+1,tr);
        }
    }
    void reset(){
        for(int i=0;i<N;i++)t[i]=1e9;
    }
    void update_min(int v,int tl,int tr,int l,int r,int x){
        if(tl>=l&&tr<=r){
            t[v]=min(t[v],x);
            return;
        }
        if(tl>r||tr<l)return;
        int tm=(tl+tr)/2;
        update_min(v*2,tl,tm,l,r,x);
        update_min(v*2+1,tm+1,tr,l,r,x);
    }
    void update_max(int v,int tl,int tr,int l,int r,int x){
        if(tl>=l&&tr<=r){
            t[v]=max(t[v],x);
            return;
        }
        if(tl>r||tr<l)return;
        int tm=(tl+tr)/2;
        update_max(v*2,tl,tm,l,r,x);
        update_max(v*2+1,tm+1,tr,l,r,x);
    }
    int query_max(int v){
        v=M[{v,v}];
        int ans=-1e9;
        while(v){
            ans=max(ans,t[v]);
            v/=2;
        }
        return ans;
    }
    int query_min(int v){
        v=M[{v,v}];
        int ans=1e9;
        while(v){
            ans=min(ans,t[v]);
            v/=2;
        }
        return ans;
    }
}seg;
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    for(int i=0;i<n;i++)finalHeight[i]=0;
    if(n<=10000&&k<=5000){
        for(int i=0;i<k;i++){
            if(op[i]==1){
                for(int j=left[i];j<=right[i];j++)finalHeight[j]=max(finalHeight[j],height[i]);
            }
            else {
                for(int j=left[i];j<=right[i];j++)finalHeight[j]=min(finalHeight[j],height[i]);
            }
        }
        return;
    }
    seg.build(1,0,n-1);
    for(int i=0;i<k;i++){
        if(op[i]==2)break;
        seg.update_max(1,0,n-1,left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        int u=seg.query_max(i);
        finalHeight[i]=u;
    }
    seg.reset();
    for(int i=0;i<n;i++)seg.update_min(1,0,n-1,i,i,finalHeight[i]);
    for(int i=0;i<k;i++){
        if(op[i]==1)continue;
        seg.update_min(1,0,n-1,left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=seg.query_min(i);
    }
}/*
int main(){
    int n,k;
    cin>>n>>k;
    int op[k];
    int l[k];
    int r[k];
    int x[k];
    for(int i=0;i<k;i++)cin>>op[i]>>l[i]>>r[i]>>x[i];
    int ans[n];
    for(int i=0;i<n;i++)ans[i]=0;
    buildWall(n,k,op,l,r,x,ans);
    for(int i=0;i<n;i++)cout<<ans[i]<<" ";
}*/
/*
10
6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0



10
4
1 1 8 4
1 0 5 3
1 2 2 5
2 6 7 0
3 4 5 4 4 4 0 0 4 0
*/

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