Submission #1273952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273952		zagaro	Wall (IOI14_wall)	C++20	100 / 100	467 ms	167424 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
vector<ll> vec;
vector<pair<ll,ll> > tr;
void build(ll ind, ll l, ll r){
    if(l == r){tr[ind]={0,0};return ;}
    build(ind*2, l, (l+r)/2);
    build(ind*2+1, (l+r)/2+1, r);
    return ;
}
void fun(ll ind, ll l, ll r, ll x, ll y, ll a, ll b){
    if(y < l || x > r)return ;
    if(x <= l && r <= y){
        if(b <= tr[ind].first)tr[ind] = {b, b};
        else if(a >= tr[ind].second)tr[ind] = {a, a};
        else {
            tr[ind].first = max(tr[ind].first, a);
            tr[ind].second = min(tr[ind].second, b);
        }
        return ;
    }
    if(tr[ind] != make_pair(ll(-1), LONG_LONG_MAX)){
        fun(ind*2, l, (l+r)/2, l, (l+r)/2, tr[ind].first, tr[ind].second);
        fun(ind*2+1, (l+r)/2+1, r, (l+r)/2+1, r, tr[ind].first, tr[ind].second);
        tr[ind].first = -1;
        tr[ind].second = LONG_LONG_MAX;
    }
    fun(ind*2, l, (l+r)/2, x, y, a, b);
    fun(ind*2+1, (l+r)/2+1, r, x, y, a, b);
    return ;
}
void fin(ll ind, ll l, ll r, ll a, ll b){
    if(b <= tr[ind].first)tr[ind] = {b, b};
    else if(a >= tr[ind].second)tr[ind] = {a, a};
    else {
        tr[ind].first = max(tr[ind].first, a);
        tr[ind].second = min(tr[ind].second, b);
    }
    if(l == r){vec[l]= max(tr[ind].first, a);return ;}
    fin(ind*2, l, (l+r)/2, tr[ind].first, tr[ind].second);
    fin(ind*2+1, (l+r)/2+1, r, tr[ind].first, tr[ind].second);
    return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vec.assign(n+1, 0);
    tr.assign(4*n+1, {-1, LONG_LONG_MAX});
    build(1, 1, n);
    for(int i=0;i<k;i++){
        op[i]==1?fun(1, 1, n, left[i]+1, right[i]+1, height[i], LONG_LONG_MAX):fun(1, 1, n, left[i]+1, right[i]+1, -1, height[i]);
    }
    fin(1, 1, n, -1, LONG_LONG_MAX);
    for(int i=1;i<=n;i++){finalHeight[i-1] = vec[i];}
    return;
}

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