Submission #474255

#	Time	Username	Problem	Language	Result	Execution time	Memory
474255		ljuba	Wall (IOI14_wall)	C++17	100 / 100	1125 ms	64924 KiB

wall

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

using namespace std;

const int mxN = 2e6 + 12;

const int INF = 1e9 + 12;

struct node {
    int mn, mx;
}st[4*mxN];

int n;

void build(int i = 1, int l2 = 0, int r2 = n-1) {
    st[i].mn = INF;
    st[i].mx = -INF;
    if(l2 == r2) {
        return;
    }

    int m2 = (l2 + 2) / 2;
    build(2*i, l2, m2);
    build(2*i+1, m2+1, 2);
}

inline void assignMin(int i, int x) {
    st[i].mn = min(st[i].mn, x);
    st[i].mx = min(st[i].mx, x);
}

inline void assignMax(int i, int x) {
    st[i].mn = max(st[i].mn, x);
    st[i].mx = max(st[i].mx, x);
}

inline void push(int i) {
    assignMin(2*i, st[i].mn);
    assignMax(2*i, st[i].mx);
    assignMin(2*i+1, st[i].mn);
    assignMax(2*i+1, st[i].mx);

    st[i].mn = INF;
    st[i].mx = -INF;
}

void minimum(int l1, int r1, int x, int i = 1, int l2 = 0, int r2 = n-1) {
    if(l1 <= l2 && r2 <= r1) {
        assignMin(i, x);
        return;
    }

    push(i);
    int m2 = (l2 + r2) / 2;
    if(l1 <= m2) minimum(l1, r1, x, 2*i, l2, m2);
    if(m2 < r1) minimum(l1, r1, x, 2*i+1, m2+1, r2);
}

void maximum(int l1, int r1, int x, int i = 1, int l2 = 0, int r2 = n-1) {
    if(l1 <= l2 && r2 <= r1) {
        assignMax(i, x);
        return;
    }

    push(i);
    int m2 = (l2 + r2) / 2;
    if(l1 <= m2) maximum(l1, r1, x, 2*i, l2, m2);
    if(m2 < r1) maximum(l1, r1, x, 2*i+1, m2+1, r2);
}

int query(int l1, int i = 1, int l2 = 0, int r2 = n-1) {
    if(l2 == r2) {
        assert(st[i].mn == st[i].mx);
        return st[i].mn;
    }

    push(i);
    int m2 = (l2 + r2) / 2;
    if(l1 <= m2) return query(l1, 2*i, l2, m2);
    else return query(l1, 2*i+1, m2+1, r2);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    //for(int i = 0; i < n; ++i) {
        //cerr << 0 << " ";
    //}
    cerr << endl;
    for(int i = 0; i < k; ++i) {
        if(op[i] == 1) {
            maximum(left[i], right[i], height[i]);
        } else {
            minimum(left[i], right[i], height[i]);
        }

        //for(int i = 0; i < n; ++i) {
            //cerr << query(i) << " ";
        //}
        //cerr << endl;
    }

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

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