Submission #623362

#	Time	Username	Problem	Language	Result	Execution time	Memory
623362		M_W	Wall (IOI14_wall)	C++17	100 / 100	844 ms	132132 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ii pair<int, int>
using namespace std;

int t[2000002 << 2][2], lazy[2000002 << 2][2]; // lower, upper

void push(int v){
    // Do something
    if(lazy[v][0] == 0 && lazy[v][1] == INT_MAX) return;
    t[v * 2][0] = max(t[v * 2][0], lazy[v][0]);
    t[v * 2 + 1][0] = max(t[v * 2 + 1][0], lazy[v][0]);
    t[v * 2][1] = max(t[v * 2][1], lazy[v][0]);
    t[v * 2 + 1][1] = max(t[v * 2 + 1][1], lazy[v][0]);

    lazy[v * 2][0] = max(lazy[v * 2][0], lazy[v][0]);
    lazy[v * 2 + 1][0] = max(lazy[v * 2 + 1][0], lazy[v][0]);
    lazy[v * 2][1] = max(lazy[v * 2][1], lazy[v][0]);
    lazy[v * 2 + 1][1] = max(lazy[v * 2 + 1][1], lazy[v][0]);

    t[v * 2][0] = min(t[v * 2][0], lazy[v][1]);
    t[v * 2 + 1][0] = min(t[v * 2 + 1][0], lazy[v][1]);
    t[v * 2][1] = min(t[v * 2][1], lazy[v][1]);
    t[v * 2 + 1][1] = min(t[v * 2 + 1][1], lazy[v][1]);

    lazy[v * 2][0] = min(lazy[v * 2][0], lazy[v][1]);
    lazy[v * 2 + 1][0] = min(lazy[v * 2 + 1][0], lazy[v][1]);
    lazy[v * 2][1] = min(lazy[v * 2][1], lazy[v][1]);
    lazy[v * 2 + 1][1] = min(lazy[v * 2 + 1][1], lazy[v][1]);

    lazy[v][0] = 0; lazy[v][1] = INT_MAX;
}

void ins(int v, int tl, int tr, int l, int r, int type, int val){
    if(l > r) return;
    if(tl == l && tr == r){
        if(type == 1){
            // shift lower
            t[v][0] = max(t[v][0], val);
            t[v][1] = max(t[v][1], val);

            lazy[v][0] = max(lazy[v][0], val);
            lazy[v][1] = max(lazy[v][1], val);
        }
        else{
            // shift upper;
            t[v][0] = min(t[v][0], val);
            t[v][1] = min(t[v][1], val);

            lazy[v][0] = min(lazy[v][0], val);
            lazy[v][1] = min(lazy[v][1], val);
        }
        return;
    }
    push(v);
    int tm = (tl + tr) >> 1;
    ins(v * 2, tl, tm, l, min(r, tm), type, val);
    ins(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, type, val);

    t[v][0] = min(t[v * 2][0], t[v * 2 + 1][0]);
    t[v][1] = max(t[v * 2][1], t[v * 2 + 1][1]);
}

int query(int v, int tl, int tr, int pos){
    if(tl == pos && tr == pos) return t[v][0];
    push(v);

    int tm = (tl + tr) >> 1;
    if(pos <= tm) return query(v * 2, tl, tm, pos);
    else return query(v * 2 + 1, tm + 1, tr, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i <= n << 2; i++) lazy[i][1] = INT_MAX;
    for(int i = 0; i < k; i++){
      ins(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }
    for(int i = 0; i < n; i++){
      finalHeight[i] = query(1, 0, n - 1, i);
    }
    return;
}

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