Submission #253391

#	Time	Username	Problem	Language	Result	Execution time	Memory
253391		ChrisT	Wall (IOI14_wall)	C++17	100 / 100	757 ms	110268 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MN = 2e6+5;
#define lc ind<<1
#define rc ind<<1|1
struct Node {
	int l,r,mx,mn;
} tree[MN<<2];
int ans[MN];
int le[MN], ri[MN], o[MN], he[MN], f[MN];
void build (int ind, int l, int r) {
	tree[ind] = {l,r,0,INT_MAX};
	if (l == r) return;
	int mid = (l+r)>>1;
	build(lc,l,mid), build(rc,mid+1,r);
}
void remove (int ind, int v) {
    tree[ind].mn = min(tree[ind].mn,v);
    tree[ind].mx = min(tree[ind].mx,v);
}
void add (int ind, int v) {
    tree[ind].mx = max(tree[ind].mx,v);
    tree[ind].mn = max(tree[ind].mn,v);
}
void push_down (int ind) {
    if (tree[ind].l == tree[ind].r) return;
    add(lc,tree[ind].mx);
    remove(lc,tree[ind].mn);
    add(rc,tree[ind].mx);
    remove(rc,tree[ind].mn);
    tree[ind].mx = 0, tree[ind].mn = INT_MAX;
}
void update (int ind, int l, int r, bool op, int v) {
    if (tree[ind].l > r || tree[ind].r < l) return;
    if (tree[ind].l >= l && tree[ind].r <= r) {
   	 op ? remove(ind,v) : add(ind,v);
   	 return;
    }
    push_down(ind);
    update(lc,l,r,op,v);
    update(rc,l,r,op,v);
}
void finish (int ind) {
    if (tree[ind].l == tree[ind].r) {
        ans[tree[ind].l] = min(tree[ind].mn,tree[ind].mx);
        return;
    }
    push_down(ind);
    finish (lc); finish (rc);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1,0,n-1);
    for (int i = 0; i < k; i++) {
   	 update(1,left[i],right[i],op[i] == 2,height[i]);
    }
    finish(1);
    for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

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