Submission #1191441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191441		Aliyyiakbar	Wall (IOI14_wall)	C++20	100 / 100	1223 ms	76512 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
using namespace std;

const int sz = 2e6 + 9;
const int INF = 1e9;

int tmax[sz << 2], tmin[sz << 2];

void add(int pos, int maxi, int mind)
{
    if (tmax[pos] > mind)
        tmax[pos] = tmin[pos] = mind;
    else if (tmin[pos] < maxi)
        tmax[pos] = tmin[pos] = maxi;
    else
    {
        tmax[pos] = max(tmax[pos], maxi);
        tmin[pos] = min(tmin[pos], mind);
    }
}

void push(int pos, int ind, int fim)
{
    if (ind != fim)
    {
        add(pos << 1, tmax[pos], tmin[pos]);
        add(pos << 1 | 1, tmax[pos], tmin[pos]);
        tmax[pos] = 0;
        tmin[pos] = INF;
    }
}

void upd(int pos, int ind, int fim, int l, int r, int maxi, int mind)
{
    push(pos, ind, fim);
    if (l <= ind && fim <= r)
    {
        add(pos, maxi, mind);
        push(pos, ind, fim);
        return;
    }
    if (r < ind || fim < l)
    {
        return;
    }
    int m = (ind + fim) >> 1;
    upd(pos << 1, ind, m, l, r, maxi, mind);
    upd(pos << 1 | 1, m + 1, fim, l, r, maxi, mind);
}

void build(int pos, int ind, int fim, int res[])
{
    if (ind == fim)
    {
        res[ind] = tmax[pos];
        return;
    }
    push(pos, ind, fim);
    int m = (ind + fim)/2;
    build(pos << 1, ind, m, res);
    build(pos << 1 | 1, m + 1, fim, res);
}

void buildWall(int n, int q, int op[], int ls[], int rs[], int hs[], int res[])
{
    for (int i = 1; i <= (n << 2); ++i)
    {
        tmin[i] = INF;
    }
    for (int i = 0; i < q; ++i)
    {
        if (op[i] == 1)
        {
            upd(1, 0, n-1, ls[i], rs[i], hs[i], INF);
        }
        else
        {
            upd(1, 0, n-1, ls[i], rs[i], 0, hs[i]);
        }
    }
    build(1, 0, n-1, res);
}

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