oj.uz

Submission #1062876

# Submission time Handle Problem Language Result Execution time Memory
1062876 2024-08-17T11:27:48 Z andrei_iorgulescu Wall (IOI14_wall) C++14
100 / 100
 547 ms 67152 KB 
#include <bits/stdc++.h>
#include "wall.h"
#warning That's not FB, that's my FB

using namespace std;

vector<int> lol;

struct node
{
    int mn = 0, mx = 1e9;
};

node aint[8000005];

void prop(int nod, int l, int r)
{
    if (l == r)
        return;
    aint[2 * nod].mx = min(aint[2 * nod].mx, aint[nod].mx);
    aint[2 * nod + 1].mx = min(aint[2 * nod + 1].mx, aint[nod].mx);
    aint[2 * nod].mx = max(aint[2 * nod].mx, aint[nod].mn);
    aint[2 * nod + 1].mx = max(aint[2 * nod + 1].mx, aint[nod].mn);
    aint[2 * nod].mn = min(aint[2 * nod].mn, aint[nod].mx);
    aint[2 * nod + 1].mn = min(aint[2 * nod + 1].mn, aint[nod].mx);
    aint[2 * nod].mn = max(aint[2 * nod].mn, aint[nod].mn);
    aint[2 * nod + 1].mn = max(aint[2 * nod + 1].mn, aint[nod].mn);
    aint[nod].mn = 0;
    aint[nod].mx = 1e9;
}

void update(int nod, int l, int r, int st, int dr, int tip, int h)
{
    if (r < st or dr < l)
        return;
    prop(nod,l,r);
    if (st <= l and r <= dr)
    {
        if (tip == 1)
        {
            aint[nod].mn = max(aint[nod].mn,h);
            aint[nod].mx = max(aint[nod].mx,h);
        }
        else
        {
            aint[nod].mn = min(aint[nod].mn,h);
            aint[nod].mx = min(aint[nod].mx,h);
        }
        return;
    }
    int mij = (l + r) / 2;
    update(2 * nod,l,mij,st,dr,tip,h);
    update(2 * nod + 1,mij + 1,r,st,dr,tip,h);
}

void dfs(int nod, int l, int r)
{
    if (l == r)
        lol[l - 1] = aint[nod].mn;
    else
    {
        prop(nod,l,r);
        int mij = (l + r) / 2;
        dfs(2 * nod,l,mij);
        dfs(2 * nod + 1,mij + 1,r);
    }
}

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    lol.resize(n);
    for (int i = 0; i < k; i++)
    {
        left[i]++;
        right[i]++;
        update(1,1,n,left[i],right[i],op[i],height[i]);
    }
    dfs(1,1,n);
    for (int i = 0; i < n; i++)
        finalHeight[i] = lol[i];
}

Compilation message

wall.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 78 ms 8236 KB Output is correct
3 Correct 120 ms 4176 KB Output is correct
4 Correct 359 ms 11088 KB Output is correct
5 Correct 197 ms 11600 KB Output is correct
6 Correct 188 ms 11600 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 79 ms 8272 KB Output is correct
9 Correct 122 ms 4176 KB Output is correct
10 Correct 349 ms 11088 KB Output is correct
11 Correct 206 ms 11604 KB Output is correct
12 Correct 227 ms 11600 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 80 ms 8072 KB Output is correct
15 Correct 20 ms 1628 KB Output is correct
16 Correct 360 ms 11344 KB Output is correct
17 Correct 202 ms 11600 KB Output is correct
18 Correct 208 ms 11344 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 77 ms 8020 KB Output is correct
9 Correct 120 ms 4332 KB Output is correct
10 Correct 357 ms 11176 KB Output is correct
11 Correct 212 ms 11600 KB Output is correct
12 Correct 195 ms 11804 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 81 ms 8276 KB Output is correct
15 Correct 21 ms 1624 KB Output is correct
16 Correct 365 ms 11388 KB Output is correct
17 Correct 211 ms 11344 KB Output is correct
18 Correct 201 ms 11348 KB Output is correct
19 Correct 509 ms 67152 KB Output is correct
20 Correct 525 ms 64592 KB Output is correct
21 Correct 513 ms 66896 KB Output is correct
22 Correct 525 ms 64544 KB Output is correct
23 Correct 507 ms 64336 KB Output is correct
24 Correct 512 ms 64384 KB Output is correct
25 Correct 522 ms 64304 KB Output is correct
26 Correct 510 ms 66880 KB Output is correct
27 Correct 521 ms 66928 KB Output is correct
28 Correct 531 ms 64336 KB Output is correct
29 Correct 547 ms 64416 KB Output is correct
30 Correct 525 ms 64336 KB Output is correct