Submission #333481

#	Time	Username	Problem	Language	Result	Execution time	Memory
333481		wildturtle	Wall (IOI14_wall)	C++14	0 / 100	1 ms	364 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector < pair < int, int > > tree;
void apply(int node,int L,int R) {
    tree[node].first=max(min(tree[node].first,R),L);
    tree[node].second=max(min(tree[node].second,R),L);
}
void push(int node,int le,int ri) {
    if(le<ri) {
        apply(2*node,tree[node].first,tree[node].second);
        apply(2*node+1,tree[node].first,tree[node].second);
    }
    tree[node].second=1e9+3;
    tree[node].first=0;
}
void go(int node,int le,int ri,int finalHeight[]) {
    if(le==ri) { finalHeight[le]=tree[node].first; return; }
    push(node,le,ri);
    go(2*node,le,(le+ri)/2,finalHeight);
    go(2*node+1,(le+ri)/2,ri,finalHeight);
}
void update(int node,int le,int ri,int start,int end,int cur1,int cur2) {
    if(ri<start || le>end) return;
    if(start<=le && ri<=end) { apply(node,cur1,cur2); return; }
    push(node,le,ri);
    update(2*node,le,(le+ri)/2,start,end,cur1,cur2);
    update(2*node+1,(le+ri)/2,ri,start,end,cur1,cur2);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]) {
    tree.resize(4*n+1);
    for(int i=1;i<=k;i++) {
        if(op[i]==1) update(1,1,n,left[i],right[i],height[i],1e9+5);
        else update(1,1,n,left[i],right[i],-(1e9+5),height[i]);
    }
    go(1,1,n,finalHeight);
}

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