Submission #1161685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161685		kl0989e	벽 (IOI14_wall)	C++20	100 / 100	541 ms	117824 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

vi tempans;

struct segTree {
    struct node {
        int val=0,mn=1e9,mx=-1e9;

        node(int _val=0, int _mn=1e9, int _mx=-1e9): val(_val),mn(_mn),mx(_mx) {}
    };

    vector<node> nodes;
    int sze;

    void push(int v, int tl, int tr) {
        if (tl!=tr) {
            nodes[2*v].mn=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v].mn));
            nodes[2*v].mx=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v].mx));
            nodes[2*v+1].mn=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v+1].mn));
            nodes[2*v+1].mx=min(nodes[v].mn,max(nodes[v].mx,nodes[2*v+1].mx));
        }
        else {
            nodes[v].val=min(nodes[v].mn,max(nodes[v].mx,nodes[v].val));
        }
        nodes[v].mn=1e9;
        nodes[v].mx=-1e9;
    }

    segTree(int n): sze(n) {
        nodes.resize(4*sze);
    }

    void update(int v, int l, int r, int val, bool mx, int tl, int tr) {
        push(v,tl,tr);
        if (l<=tl && tr<=r) {
            if (mx) {
                nodes[v].mx=max(nodes[v].mx,val);
                nodes[v].mn=max(nodes[v].mn,val);
            }
            else {
                nodes[v].mx=min(nodes[v].mx,val);
                nodes[v].mn=min(nodes[v].mn,val);
            }
            push(v,tl,tr);
            return;
        }
        if (r<tl || tr<l) {
            return;
        }
        int tm=tl+(tr-tl)/2;
        update(2*v,l,r,val,mx,tl,tm);
        update(2*v+1,l,r,val,mx,tm+1,tr);
    }
    void update(int l, int r, int val, bool mx) {
        update(1,l,r,val,mx,0,sze-1);
    }

    void travel(int v, int tl, int tr) {
        push(v,tl,tr);
        if (tl==tr) {
            tempans[tl]=nodes[v].val;
            return;
        }
        int tm=tl+(tr-tl)/2;
        travel(2*v,tl,tm);
        travel(2*v+1,tm+1,tr);
    }
    void travel() {
        travel(1,0,sze-1);
    }
};

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    tempans.resize(n);
    segTree data(n);
    for (int i=0; i<k; i++) {
        data.update(l[i],r[i],h[i],op[i]==1);
    }
    data.travel();
    for (int i=0; i<n; i++) {
        ans[i]=tempans[i];
    }
}

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