Submission #1112451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112451		farica	Wall (IOI14_wall)	C++14	0 / 100	1 ms	504 KiB

wall

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

using namespace std;

const int MAX_N = 1e5;

struct Segm {
    int L, R;
};

vector<Segm>segm;

void push(int pos, int l, int r) {
    if(l==r) return;
    segm[2*pos+1].L = max(segm[2*pos+1].L, segm[pos].L);
    segm[2*pos+1].R = min(segm[2*pos+1].R, segm[pos].R);
    segm[2*pos+1].R = max(segm[2*pos+1].R, segm[2*pos+1].L);
    segm[2*pos+2].L = max(segm[2*pos+2].L, segm[pos].L);
    segm[2*pos+2].R = min(segm[2*pos+2].R, segm[pos].R);
    segm[2*pos+2].R = max(segm[2*pos+2].R, segm[2*pos+2].L);
    segm[pos].L = 0;
    segm[pos].R = MAX_N;
}

void update(int pos, int l, int r, int L, int R, int val, int type) {
    if(r < L or l > R) return;
    push(pos, l, r);
    if(l >= L && r <= R) {
        if(type == 1) {
            segm[pos].L = max(segm[pos].L, val);
            segm[pos].R = (segm[pos].L > segm[pos].R) ? segm[pos].L : segm[pos].R;
        } else {
            segm[pos].R = min(segm[pos].R, val);
            segm[pos].L = (segm[pos].R < segm[pos].L) ? segm[pos].R : segm[pos].L;
        }
        return;
    }
    int mid = (l+r)/2;
    update(2*pos+1, l, mid, L, R, val, type);
    update(2*pos+2, mid+1, r, L, R, val, type);
}

int query(int pos, int l, int r, int x) {
    if(l == r) return segm[pos].L;
    int mid = (l+r)/2;
    if(mid >= x) return query(2*pos+1, l, mid, x);
    else return query(2*pos+2, mid+1, r, x);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segm tmp;
    tmp.L = 0;
    tmp.R = MAX_N;
    segm.assign(8*n, tmp);
    for(int i=0; i<k; ++i) {
        update(1, 1, n, left[i], right[i], height[i], op[i]);
    }
    for(int i=1; i<=n; ++i) {
        finalHeight[i-1] = query(1, 1, n, i);
    }
}

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