Submission #1102103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102103		alexander707070	Wall (IOI14_wall)	C++14	100 / 100	516 ms	95428 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"

#define MAXN 2000007
using namespace std;

int n,q;
int s[MAXN];

struct ST{
    struct node{
        int mins,maxs;
        int lazy;

        inline friend node operator + (node fr,node sc){
            return {min(fr.mins,sc.mins),max(fr.maxs,sc.maxs),-1};
        }
    };

    node tree[4*MAXN];

    void psh(int v){
        if(tree[v].lazy==-1)return;

        tree[2*v].maxs=tree[2*v].mins=tree[2*v].lazy=tree[v].lazy;
        tree[2*v+1].maxs=tree[2*v+1].mins=tree[2*v+1].lazy=tree[v].lazy;

        tree[v].lazy=-1;
    }

    void add(int v,int l,int r,int ll,int rr,int val){
        if(ll>rr)return;

        if(l==ll and r==rr and tree[v].maxs==tree[v].mins){
            if(tree[v].maxs<val){
                tree[v].maxs=tree[v].mins=val;
                tree[v].lazy=val;
            }
            return;
        }

        int tt=(l+r)/2;
        psh(v);

        add(2*v,l,tt,ll,min(tt,rr),val);
        add(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

        tree[v]=tree[2*v]+tree[2*v+1];
    }

    void rem(int v,int l,int r,int ll,int rr,int val){
        if(ll>rr)return;

        if(l==ll and r==rr and tree[v].maxs==tree[v].mins){
            if(tree[v].maxs>val){
                tree[v].maxs=tree[v].mins=val;
                tree[v].lazy=val;
            }
            return;
        }

        int tt=(l+r)/2;
        psh(v);

        rem(2*v,l,tt,ll,min(tt,rr),val);
        rem(2*v+1,tt+1,r,max(tt+1,ll),rr,val);

        tree[v]=tree[2*v]+tree[2*v+1];
    }

    void solve(int v,int l,int r){
        if(l==r){
            s[l]=tree[v].maxs;
        }else{
            int tt=(l+r)/2;
            psh(v);

            solve(2*v,l,tt);
            solve(2*v+1,tt+1,r);
        }
    }
}seg;

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
//void buildWall(int N, int K, vector<int> op,vector<int> left, vector<int> right, vector<int> height){
    
    n=N; q=K;

    for(int i=0;i<q;i++){
        left[i]++;
        right[i]++;

        if(op[i]==1){
            seg.add(1,1,n,left[i],right[i],height[i]);
        }else{
            seg.rem(1,1,n,left[i],right[i],height[i]);
        }
    }

    seg.solve(1,1,n);

    for(int i=1;i<=n;i++){
        finalHeight[i-1]=s[i];
    }

    return;
}

/*int main(){

    buildWall(10,6,{1,2,2,1,1,2},{1,4,3,0,2,6},{8,9,6,5,2,7},{4,1,5,3,5,0});

	return 0;
}*/

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