Submission #1146996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146996		brianhdzmdo	Wall (IOI14_wall)	C++20	0 / 100	73 ms	8336 KiB

wall

#include <algorithm>
#include <cmath>
#include <iostream>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include <climits>

#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define ll long long
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define fr1(i, a, b) for (ll i = a - 1; i >= b; i--)
#define fi first
#define se second
#define mp(j, k) make_pair(j, k)
#define pb(x) push_back(x)
#define pbp(x, y) push_back({x, y})
#define in(x) insert(x)
#define vec vector<ll>
#define vecv vector<vector<ll> >
#define veb vector<bool>
#define vecp vector<pair<ll,ll>>
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define ac 1e-7
#define fauto(a)   \
  for (auto i : a) \
    cout << i << " ";
#define fautop(a)  \
  for (auto i : a) \
    cout << i.fi << " " << i.se << endl;

using namespace std;

const int N = 2e6 + 5;

int ST[4 * N];
int lazyMax[4 * N], lazyMin[4 * N];

void init()
{
    fill(lazyMax, lazyMax + 4 * N, -1);
    fill(lazyMin, lazyMin + 4 * N, 1e9);
}

void propagate(int node, int l, int r)
{
    if(lazyMax[node] != -1) //máximo
     {
        ST[node] = max(lazyMax[node], ST[node]);
        if(l != r)
        {
            int left = node * 2 + 1;
            int right = node * 2 + 2;
            lazyMax[left] = max(lazyMax[left], lazyMax[node]);
            lazyMax[right] = max(lazyMax[right], lazyMax[node]);
        }
        lazyMax[node] = -1;
     }

     if(lazyMin[node] != 1e9)
     {
        ST[node] = min(lazyMin[node], ST[node]);
        if(l != r)
        {
            int left = node * 2 + 1;
            int right = node * 2 + 2;

            lazyMin[left] = min(lazyMin[left], lazyMin[node]);
            lazyMin[right] = min(lazyMin[right], lazyMin[node]);
        }
        lazyMin[node] = 1e9;
     }
}

void updateMax(int node, int l, int r, int a, int b, int h)
{
    propagate(node, l, r);

    if(l > b || r < a) return;

    if(l <= a && b <= r)
    {
        lazyMax[node] = max(lazyMax[node], h);
        propagate(node, l, r);
        return;
    }

    int mid = (l + r) / 2;
    int left = node * 2 + 1;
    int right = node * 2 + 2;

    updateMax(left, l, mid, a, b, h);
    updateMax(right, mid + 1, r, a, b, h);

    ST[node] = max(ST[left], ST[right]);
}

void updateMin(int node, int l, int r, int a, int b, int h)
{
    propagate(node, l, r);

    if(l > b || r < a) return;

    if(l <= a && b <= r)
    {
        lazyMin[node] = min(lazyMin[node], h);
        propagate(node, l, r);
        return;
    }

    int mid = (l + r) / 2;
    int left = node * 2 + 1;
    int right = node * 2 + 2;

    updateMin(left, l, mid, a, b, h);
    updateMin(right, mid + 1, r, a, b, h);

    ST[node] = min(ST[left], ST[right]);
}

int query(int node, int l, int r, int pos)
{
    propagate(node, l, r);

    if(l == r) return ST[node];

    int mid = (l + r) / 2;
    int left = node * 2 + 1;
    int right = node * 2 + 2;

    if(pos <= mid) return query(left, l, mid, pos);
    else return query(right, mid + 1, r, pos);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
   fr(i, 0, k)
   {
        ll ax = op[i];
        ll a = left[i];
        ll b = right[i];
        ll h = height[i];

        if(ax == 1) 
        {
            updateMax(0, 0, n - 1, a, b, h);
        }
        else
            updateMin(0, 0, n - 1, a, b, h);
   }

   fr(i, 0, n)
    finalHeight[i] = query(0, 0, n - 1, i);
}

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