Submission #1103990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103990		vjudge1	Wall (IOI14_wall)	C++17	100 / 100	623 ms	62280 KiB

wall

#include "wall.h"
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2000000;
pair<int,int> seg[4*N+7];

void push(int l,int r,int node){
    if(l==r) return ;
    int ll=node*2;
    int rr=node*2+1;
    seg[ll].first = min(seg[ll].first, seg[node].first);
    seg[ll].first = max(seg[ll].first, seg[node].second);
    seg[ll].second = min(seg[ll].second, seg[node].first);
    seg[ll].second = max(seg[ll].second, seg[node].second);
    seg[rr].first = min(seg[rr].first, seg[node].first);
    seg[rr].first = max(seg[rr].first, seg[node].second);
    seg[rr].second = min(seg[rr].second, seg[node].first);
    seg[rr].second = max(seg[rr].second, seg[node].second);
}

void update(int l,int r,int idx1,int idx2,int val,int node,int mode){
    push(l,r,node);
    if(l>idx2 || r<idx1) return ;
    if(l>=idx1 && r<=idx2){
        if(mode){
            seg[node].first=min(seg[node].first,val);
            seg[node].second=min(seg[node].second,val);
        }
        else{
            seg[node].first=max(seg[node].first,val);
            seg[node].second=max(seg[node].second,val);
        }
        return ;
    }
    seg[node].first=1e9;
    seg[node].second=-1e9;
    int mid=(l+r)>>1;
    update(l,mid,idx1,idx2,val,node*2,mode);
    update(mid+1,r,idx1,idx2,val,node*2+1,mode);
}

void query(int l,int r,int node, int arr[]){
    if(l==r){
        arr[l-1]=seg[node].first;
        return ;
    }
    push(l,r,node);
    int mid=(l+r)>>1;
    query(l,mid,node*2,arr);
    query(mid+1,r,node*2+1,arr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; ++i) {
        update(1,n,left[i]+1,right[i]+1,height[i],1,op[i]-1);
    }
    query(1,n,1,finalHeight);
    return;
}

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