Submission #1184649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184649		Warinchai	Wall (IOI14_wall)	C++20	100 / 100	789 ms	151624 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int inf=1e6;
struct node{
    int mx,mn,mx2,mn2;
    node(int _mx=-inf,int _mn=inf,int _mx2=-inf,int _mn2=inf){
        mx=_mx,mx2=_mx2,mn=_mx,mn2=_mn2;
    }
    friend node operator+(node a,node b){
        node c;
        if(a.mx>b.mx)c.mx=a.mx,c.mx2=max(a.mx2,b.mx);
        else if(b.mx>a.mx)c.mx=b.mx,c.mx2=max(a.mx,b.mx2);
        else c.mx=a.mx,c.mx2=max(a.mx2,b.mx2);
        if(a.mn<b.mn)c.mn=a.mn,c.mn2=min(a.mn2,b.mn);
        else if(b.mn<a.mn)c.mn=b.mn,c.mn2=min(a.mn,b.mn2);
        else c.mn=a.mn,c.mn2=min(a.mn2,b.mn2);
        return c;
    }
};
struct segtree_beats{
    node info[8000005];
    void chmx(int st,int en,int i,int val){
        if(val<info[i].mn)return;
        info[i].mn=val;
        if(val>=info[i].mx)info[i].mx=val;
        else if(val>info[i].mx2)info[i].mx2=val;
    }
    void chmn(int st,int en,int i,int val){
        if(val>info[i].mx)return;
        info[i].mx=val;
        if(val<=info[i].mn)info[i].mn=val;
        else if(val<info[i].mn2)info[i].mn2=val;
    }
    void push(int st,int en,int i){
        int m=(st+en)/2;
        chmx(st,m,i*2,info[i].mn);
        chmx(m+1,en,i*2+1,info[i].mn);
        chmn(st,m,i*2,info[i].mx);
        chmn(m+1,en,i*2+1,info[i].mx);
    }
    void chmax(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l||val<=info[i].mn)return;
        //cerr<<st<<" "<<en<<"\n";
        if(st>=l&&en<=r&&val<info[i].mn2){
            chmx(st,en,i,val);
            //cerr<<"change mn into:"<<info[i].mn<<" "<<info[i].mx<<"\n";
            return;
        }
        int m=(st+en)/2;
        push(st,en,i);
        chmax(st,m,i*2,l,r,val);
        chmax(m+1,en,i*2+1,l,r,val);
        info[i]=info[i*2]+info[i*2+1];
        //cerr<<st<<' '<<en<<" turns into "<<info[i].mn<<" "<<info[i].mn2<<" "<<info[i].mx<<" "<<info[i].mx2<<"\n";
    }
    void chmin(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l||val>=info[i].mx)return;
        if(st>=l&&en<=r&&val>info[i].mx2)return chmn(st,en,i,val);
        int m=(st+en)/2;
        push(st,en,i);
        chmin(st,m,i*2,l,r,val);
        chmin(m+1,en,i*2+1,l,r,val);
        info[i]=info[i*2]+info[i*2+1];
    }
    int fans(int st,int en,int i,int pos){
        if(st==en)return info[i].mx;
        push(st,en,i);
        int m=(st+en)/2;
        if(pos<=m)return fans(st,m,i*2,pos);
        else return fans(m+1,en,i*2+1,pos);
    }
    void build(int st,int en,int i){
        info[i]=node(0,0);
        if(st==en)return;
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
    }
}tr;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    tr.build(1,n,1);
    //cerr<<"work\n";
    for(int i=0;i<k;i++){
        if(op[i]==1){
            //cerr<<"chmax\n";
            tr.chmax(1,n,1,left[i]+1,right[i]+1,height[i]);
        }else{
            //cerr<<"chmin\n";
            tr.chmin(1,n,1,left[i]+1,right[i]+1,height[i]);
        }
        //cerr<<"mx:"<<tr.info[1].mx<<"\n";
        //for(int i=1;i<=n;i++)cerr<<tr.fans(1,n,1,i)<<" ";
        //cerr<<"\n";
    }
    //cerr<<"work\n";
    for(int i=1;i<=n;i++){
        finalHeight[i-1]=tr.fans(1,n,1,i);
        //cerr<<finalHeight[i-1]<<" ";
    }
    return;
}

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