제출 #1203534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203534		Quentolosse	Wall (IOI14_wall)	C++20	100 / 100	397 ms	81612 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

#define int long long

using namespace std;

struct Noeud {
    int mini = 1e9, maxi = 0;
    Noeud(int _mn = 1e9, int _mx = 0) {
        mini = _mn;
        maxi = _mx;
    }
};

Noeud fusion(Noeud avant, Noeud apres) {
    Noeud ret(min(avant.mini, apres.mini), max(avant.maxi, apres.maxi));

    if (apres.mini < ret.maxi) {
        ret.maxi = apres.mini;
    }
    if (apres.maxi > ret.mini) {
        ret.mini = apres.maxi;
    }

    return ret;
}

struct segtree {
    int taille = 1;
    vector<Noeud> tree;

    segtree(int _n) {
        while(taille < _n) taille <<= 1;
        
        tree.resize(taille*2);
    }

    void prop(int pos) {
        if (pos < taille) {
            tree[2*pos] = fusion(tree[2*pos], tree[pos]);
            tree[2*pos+1] = fusion(tree[2*pos+1], tree[pos]);
            tree[pos] = Noeud();
        }
    }

    void modif(int lr, int rr, int l, int r, int pos, Noeud m) {
        if (r <= lr || l >= rr) {
            return;
        }

        if (l >= lr && r <= rr) {
            tree[pos] = fusion(tree[pos], m);
            return;
        }

        prop(pos);

        int mid = (l+r)/2;

        modif(lr, rr, l, mid, 2*pos, m);
        modif(lr, rr, mid, r, 2*pos+1, m);
    }

};

void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalHeight[]){

    segtree mur(n);

    for (int i = 0; i < k; i++)
    {
        if (op[i] == 1) {
            mur.modif(left[i], right[i]+1, 0, mur.taille, 1, {(int)1e9, height[i]});
        }
        else {
            mur.modif(left[i], right[i]+1, 0, mur.taille, 1, {height[i], 0});
        }
    }

    for (int i = 0; i < mur.taille; i++)
    {
        mur.prop(i);
    }
    
    for (int i = 0; i < n; i++)
    {
        Noeud actuel = mur.tree[mur.taille + i];
        finalHeight[i] = actuel.maxi;
    }    
    return;

}

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