제출 #1168570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168570		alir3za_zar3	Wall (IOI14_wall)	C++20	100 / 100	727 ms	175024 KiB

wall

// Alir3za.Zar3 -> Shiraz , Iran
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN = 2e6+7;
int n,q;

const int base_min = -1;
const int base_max = mxN;
struct SEGMENT 
{
    struct NODE
    {
        int min=0 , minlzy=base_min;
        int max=0 , maxlzy=base_max;
    };
    NODE T[mxN<<2]; 
    int nw=1 , L[mxN<<2],R[mxN<<2];

    tuple<int,int,int> info 
    (int node , int l , int r)
    {
        int o=l+r>>1 , lc , rc;
        if (L[node]) lc = L[node];
        else lc = L[node] = ++nw;
        if (R[node]) rc = R[node];
        else rc = R[node] = ++nw;
        return {o , lc , rc};
    }
    void apply 
    (int typ , int v , int node , int l , int r)
    {
        if (!typ)
        {
            T[node].min = max(T[node].min,v);
            T[node].minlzy = max(T[node].minlzy,v);
            if (v > T[node].max)
                T[node].max = T[node].maxlzy = v; 
        }
        else
        {
            T[node].max = min(T[node].max,v);
            T[node].maxlzy = min(v,T[node].maxlzy);
            if (v < T[node].min)
                T[node].min = T[node].minlzy = v;
        }
    }
    void min_shifter 
    (int node , int lc , int rc , int l , int o , int r)
    {
        if (T[node].minlzy != base_min)
        {
            apply(0 , T[node].minlzy , lc , l , o);
            apply(0 , T[node].minlzy , rc , o , r);
        }
    }
    void max_shifter 
    (int node , int lc , int rc , int l , int o , int r)
    {
        if (T[node].maxlzy != base_max)
        {
            apply(1 , T[node].maxlzy , lc , l , o);
            apply(1 , T[node].maxlzy , rc , o , r);
        }
    }
    void shift 
    (int node , int l , int r)
    {
        if (l == r-1) return;
        auto [o , lc , rc] = info(node , l , r);
        
        min_shifter(node , lc , rc , l , o , r);
        max_shifter(node , lc , rc , l , o , r);

        T[node].minlzy = base_min;
        T[node].maxlzy = base_max;
    }
    void update 
    (int lq , int rq , int typ , int v , int node=1 , int l=0 , int r=n)
    {
        shift(node , l , r);
        if (r<=lq or l>=rq) return;
        if (lq<=l and r<=rq) 
        {
            apply(typ , v , node , l , r);
            return;
        }
        auto [o , lc , rc] = info(node , l , r);
        update(lq , rq , typ , v , lc , l , o);
        update(lq , rq , typ , v , rc , o , r);
        T[node].min = min(T[lc].min,T[rc].min);
        T[node].max = max(T[lc].max,T[rc].max);
    }
    int query 
    (int id , int node=1 , int l=0 , int r=n)
    {
        if (T[node].min == T[node].max) return T[node].min;
        shift(node , l , r);
        auto [o , lc , rc] = info(node , l , r);
        if (id < o) return query(id , lc , l , o);
        else return query(id , rc , o , r);
    }
} segmenT;

void buildWall (int N , int K , int op[] , int L[] , int R[] , int V[] , int out[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
        
    n = N; q = K;
    for (int i=0; i<q; i++)
    {
        int typ=op[i] , l=L[i] , r=R[i] , v=V[i];
        segmenT.update(l,++r,--typ,v);
    }
    for (int i=0; i<n; i++)
        out[i] = segmenT.query(i);
}

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