Submission #1197264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197264		TahirAliyev	Wall (IOI14_wall)	C++20	100 / 100	463 ms	96872 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
 
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pii pair<int, int>
#define ld long double
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 2e6 + 6;
int MOD = 998244353;

array<int, 2> lazy[4 * MAX];
int ans[MAX];

void add(array<int, 2> &a, array<int, 2> b){
    if(a[1] < b[0]) a = {b[0], b[0]};
    else if(b[1] < a[0]) a = {b[1], b[1]};
    else a = {max(a[0], b[0]), min(a[1], b[1])};
}

void relax(int node){
    add(lazy[2 * node], lazy[node]);
    add(lazy[2 * node + 1], lazy[node]);
    lazy[node] = {0, oo};
}

void update(int node, int l, int r, int ul, int ur, int ty, int val){
    if(ur < l || r < ul) return;
    if(l != r) relax(node);
    if(ul <= l && r <= ur){
        if(l != r) relax(node);
        if(ty == 1) add(lazy[node], {val, oo});
        else add(lazy[node], {0, val});
        return;
    }    
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, ty, val);
    update(2 * node + 1, mid + 1, r, ul, ur, ty, val);
}
void build(int node, int l, int r){
    if(l == r){
        ans[l] = lazy[node][0];
        return;
    }
    relax(node);
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i <= 4 * n; i++) lazy[i] = {0, oo};
    for(int i = 0; i < k; i++){
        update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
    }
    build(1, 0, n - 1);
    for(int i = 0; i < n; i++){
        finalHeight[i] = ans[i];
    }
}

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