oj.uz

Submission #242026

# Submission time Handle Problem Language Result Execution time Memory
242026 2020-06-26T14:45:08 Z Coroian_David Wall (IOI14_wall) C++11
100 / 100
 906 ms 77580 KB 
#include <bits/stdc++.h>

//#include "wall.h"

#define MAX_N 2000000

using namespace std;

const int MAX = 100000;
const int MIN = 0;

int rez[MAX_N + 1];
struct aint
{
    int st, dr;
};

aint arb[(MAX_N << 2) + 1];

void upd(int poz, int st, int dr, int a, int b, int x, int y)
{
    //cout << "FACEM UPD " << poz << " " << st << " " << dr << " " << " INterv " << a << " " << b << " BVAL " << x << " " << y << "\n";

    if(st == a && dr == b)
    {
        if(x > arb[poz].dr)
        {
            arb[poz] = {x, x};
        }

        else
            if(y < arb[poz].st)
                arb[poz] = {y, y};

        else
        {
            arb[poz].st = max(arb[poz].st, x);
            arb[poz].dr = min(arb[poz].dr, y);
        }

        return;
    }

    int mid = (st + dr) >> 1;

    upd(poz << 1, st, mid, st, mid, arb[poz].st, arb[poz].dr);
    upd((poz << 1) + 1, mid + 1, dr, mid + 1, dr, arb[poz].st, arb[poz].dr);

    arb[poz] = {MIN, MAX};

    if(b <= mid)
        upd(poz << 1, st, mid, a, b, x, y);

    if(a > mid)
        upd((poz << 1) + 1, mid + 1, dr, a, b, x, y);

    if(a <= mid && b > mid)
    {
        upd(poz << 1, st, mid, a, mid, x, y);
        upd((poz << 1) + 1, mid + 1, dr, mid + 1, b, x, y);
    }
}

void build(int poz, int st, int dr)
{
    arb[poz] = {MIN, MAX};

    if(st == dr)
        return;

    int mid = (st + dr) >> 1;

    build(poz << 1, st, mid);
    build((poz << 1) + 1, mid + 1, dr);
}

void dfs(int poz, int st, int dr)
{
    if(st == dr)
    {
        rez[st] = arb[poz].st;

        return;
    }

    int mid = (st + dr) >> 1;

    upd(poz << 1, st, mid, st, mid, arb[poz].st, arb[poz].dr);
    upd((poz << 1) + 1, mid + 1, dr, mid + 1, dr, arb[poz].st, arb[poz].dr);

    arb[poz] = {MIN, MAX};

    dfs(poz << 1, st, mid);
    dfs((poz << 1) + 1, mid + 1, dr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    build(1, 1, n);

    for(int i = 0; i < k; i ++)
    {
        int st = left[i] + 1;
        int dr = right[i] + 1;
        int nr = height[i];

        if(op[i] == 2)
            upd(1, 1, n, st, dr, MIN, nr);

        else
            upd(1, 1, n, st, dr, nr, MAX);
    }

    dfs(1, 1, n);

    for(int i = 0; i < n; i ++)
        finalHeight[i] = rez[i + 1];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 192 ms 14044 KB Output is correct
3 Correct 228 ms 8056 KB Output is correct
4 Correct 628 ms 20940 KB Output is correct
5 Correct 396 ms 21880 KB Output is correct
6 Correct 382 ms 20344 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 7 ms 436 KB Output is correct
4 Correct 12 ms 896 KB Output is correct
5 Correct 11 ms 944 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 181 ms 13944 KB Output is correct
9 Correct 225 ms 8060 KB Output is correct
10 Correct 597 ms 20856 KB Output is correct
11 Correct 413 ms 21880 KB Output is correct
12 Correct 368 ms 20344 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 189 ms 14072 KB Output is correct
15 Correct 51 ms 2168 KB Output is correct
16 Correct 702 ms 21112 KB Output is correct
17 Correct 387 ms 20472 KB Output is correct
18 Correct 394 ms 20472 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 11 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 189 ms 13940 KB Output is correct
9 Correct 214 ms 8056 KB Output is correct
10 Correct 592 ms 20856 KB Output is correct
11 Correct 408 ms 21856 KB Output is correct
12 Correct 394 ms 20472 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 188 ms 14072 KB Output is correct
15 Correct 46 ms 2172 KB Output is correct
16 Correct 703 ms 21076 KB Output is correct
17 Correct 391 ms 20684 KB Output is correct
18 Correct 367 ms 20600 KB Output is correct
19 Correct 863 ms 77344 KB Output is correct
20 Correct 861 ms 75016 KB Output is correct
21 Correct 861 ms 77580 KB Output is correct
22 Correct 852 ms 74996 KB Output is correct
23 Correct 831 ms 75024 KB Output is correct
24 Correct 851 ms 75040 KB Output is correct
25 Correct 874 ms 75000 KB Output is correct
26 Correct 882 ms 77432 KB Output is correct
27 Correct 869 ms 77560 KB Output is correct
28 Correct 858 ms 75000 KB Output is correct
29 Correct 881 ms 74872 KB Output is correct
30 Correct 906 ms 75160 KB Output is correct