Submission #94718

#	Time	Username	Problem	Language	Result	Execution time	Memory
94718		someone_aa	Wall (IOI14_wall)	C++17	100 / 100	1328 ms	86052 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 2000100;
const int inf = 1e9;
int n, q;

struct interval {
public:
    int l, r;
    bool mark;
};

interval tree[4*maxn];

interval un(interval a, interval b) {
    interval c = {min(a.l, b.l), max(a.r, b.r)};
    return c;
}

interval in(interval a, interval b) {
    interval c;
    if(a.r < b.l) c = {b.l, b.l};
    else if(a.l > b.r) c = {b.r, b.r};
    else c = {max(a.l, b.l), min(a.r, b.r)};
    return c;
}

interval mergef(interval a, interval b) {
    return un(a, b);
}

void set_update(interval val, int li, int ri, int index) {
    tree[index] = in(tree[index], val);
    if(li != ri) {
        tree[index].mark = true;
    }
}

void push_update(int li, int ri, int index) {
    if(tree[index].mark) {
        int mid = (li+ri)/2;
        set_update(tree[index], li, mid, 2*index);
        set_update(tree[index], mid+1, ri, 2*index+1);
        tree[index].mark = false;
    }
}

void update(int ul, int ur, interval val, int li=0, int ri=n-1, int index=1) {
    //cout<<li<<" "<<ri<<" -> "<<tree[index].l<<" "<<tree[index].r<<"\n";
    if(li > ur || ri < ul) return;
    else if(li >= ul && ri <= ur) {
        //cout<<"Updating range: ["<<li<<", "<<ri<<"] -> "<<val.l<<" "<<val.r<<"\n";
        set_update(val, li, ri, index);
    }
    else {
        int mid = (li+ri)/2;

        push_update(li, ri, index);

        update(ul,ur,val,li,mid,2*index);
        update(ul,ur,val,mid+1,ri,2*index+1);
        tree[index] = un(tree[2*index], tree[2*index+1]);
    }
}

interval query(int ul, int ur, int li=0, int ri=n-1, int index=1) {
    push_update(li, ri, index);
    if(li > ur || ri < ul) return {inf, -inf};
    else if(li >= ul && ri <= ur) {
        return tree[index];
    }
    else {
        int mid = (li+ri)/2;
        interval left_q = {inf, -inf};
        interval right_q = {inf, -inf};

        if(ul <= mid) left_q = query(ul, ur, li, mid, 2*index);
        else right_q = query(ul, ur, mid+1, ri, 2*index+1);

        tree[index] = un(tree[2*index], tree[2*index+1]);

        if(ul <= mid) return left_q;
        else return right_q;
    }
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    int q = 0;
    while(q < k) {
        int q_type = op[q];
        int x = height[q];
        int l = left[q];
        int r = right[q];

        if(q_type == 1) {
            interval up = {x, inf};
            update(l, r, up);
        }
        else {
            interval up = {-inf, x};
            update(l, r, up);
        }
        q++;
    }

    for(int i=0;i<n;i++) {
        finalHeight[i] = query(i,i).l;
    }
    return;
}

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