Submission #690950

#	Time	Username	Problem	Language	Result	Execution time	Memory
690950		TheSahib	Wall (IOI14_wall)	C++14	0 / 100	132 ms	8024 KiB

wall

#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9

using namespace std;

int N;
vector<pii> tree;

void update(int node, int l, int r, int ul, int ur, pii val){
    if(ur < l || r < ul){ return; }

    if(ul <= l && r <= ur){
        if(val.first != -oo){
            tree[node].first = max(tree[node].first, val.first);
            tree[node].second = max(tree[node].second, tree[node].first);
        }
        if(val.second != oo){
            tree[node].second = min(tree[node].second, val.second);
            tree[node].first = min(tree[node].second, tree[node].first);
        }
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2 + 1, l, mid, ul, ur, val);
    update(node * 2 + 2, mid + 1, r, ul, ur, val);
}

void ask(int node, int l, int r, int pos, pii &ans){
    ans.first = max(tree[node].first, ans.first);
    ans.second = min(tree[node].second, ans.second);
    if(l == r){ return; }
    
    int mid = (l + r) / 2;
    if(pos <= mid){
        ask(node * 2 + 1, l, mid, pos, ans);
    }
    else{
        ask(node * 2 + 2, mid + 1, r, pos, ans);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    tree.resize(N * 4, {0, oo});
    
    for (int i = 0; i < k; i++)
    {
        update(0, 0, N - 1, left[i], right[i], {(op[i] == 1) ? height[i] : -oo, (op[i] == 2) ? height[i] : oo});
    }
    
    for (int i = 0; i < N; i++)
    {
        pii a = {-oo, oo};
        ask(0, 0, N - 1, i, a);
        finalHeight[i] = a.first;
    }
}

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