Submission #1294039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294039		Faisal_Saqib	벽 (IOI14_wall)	C++20	100 / 100	588 ms	120244 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
// Ghulam Junaid 's Solution
using namespace std;

const int N = 2e6 + 10;
int n, q;

struct node{
    int mx, mn, lazy = -1;    
} seg[4 * N];

void push(int v){
    if (seg[v].lazy == -1) return;

    int lc = 2 * v, rc = lc + 1;
    
    seg[lc].mn = seg[v].lazy, seg[rc].mn = seg[v].lazy;
    seg[lc].mx = seg[v].lazy, seg[rc].mx = seg[v].lazy;

    seg[lc].lazy = seg[v].lazy, seg[rc].lazy = seg[v].lazy;
    seg[v].lazy = -1;
}

void adding(int l, int r, int val, int v = 1, int s = 0, int e = n){
    if (r <= s || e <= l) return;
    if (l <= s && e <= r){
        if (seg[v].mx <= val){
            seg[v].mx = val;
            seg[v].mn = val;
            seg[v].lazy = val;
            return;
        }
        if (seg[v].mn >= val)
            return;
    }

    push(v);

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    adding(l, r, val, lc, s, mid);
    adding(l, r, val, rc, mid, e);

    seg[v].mx = max(seg[lc].mx, seg[rc].mx);
    seg[v].mn = min(seg[lc].mn, seg[rc].mn);
}

void removing(int l, int r, int val, int v = 1, int s = 0, int e = n){
    if (r <= s || e <= l) return;
    if (l <= s && e <= r){
        if (seg[v].mx <= val)
            return;
        if (seg[v].mn >= val){
            seg[v].mx = val;
            seg[v].mn = val;
            seg[v].lazy = val;
            return;
        }
    }

    push(v);

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;

    removing(l, r, val, lc, s, mid);
    removing(l, r, val, rc, mid, e);

    seg[v].mx = max(seg[lc].mx, seg[rc].mx);
    seg[v].mn = min(seg[lc].mn, seg[rc].mn);
}

int get(int p, int v = 1, int s = 0, int e = n){
    if (e - s == 1) return seg[v].mn;
    push(v);

    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
    if (p < mid) return get(p, lc, s, mid);
    return get(p, rc, mid, e);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N, q = k;

    for (int i=0; i<q; i++){
        if (op[i] == 1)
            adding(left[i], right[i] + 1, height[i]);
        else
            removing(left[i], right[i] + 1, height[i]);
    }

    for (int i=0; i<n; i++)
        finalHeight[i] = get(i);
    for (int i=0; i<n; i++)
        if (finalHeight[i] == -1) finalHeight[i] = 0;
}

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