oj.uz

Submission #1062741

# Submission time Handle Problem Language Result Execution time Memory
1062741 2024-08-17T10:14:58 Z damjandavkov Wall (IOI14_wall) C++17
100 / 100
 932 ms 91988 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> mx, mn, wl, wr;
int p, dp, r = 2147483647;
void ac(int i, int x, int n)
{
    if (x > mn[i])
        mx[i] = mn[i] = x;
    else if (n < mx[i])
        mx[i] = mn[i] = n;
    else
    {
        mx[i] = max(mx[i], x);
        mn[i] = min(mn[i], n);
    }
}
void push(int i)
{
    if (i >= p)
        return;
    ac(i << 1, mx[i], mn[i]);
    ac((i << 1) ^ 1, mx[i], mn[i]);
    mx[i] = 0;
    mn[i] = r;
}
void upd(int l, int r, int i, int x, int n)
{
    push(i);
    if (wl[i] >= r || wr[i] <= l)
        return;
    if (wl[i] >= l && wr[i] <= r)
    {
        ac(i, x, n);
        return;
    }
    upd(l, r, i << 1, x, n);
    upd(l, r, (i << 1) ^ 1, x, n);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    p = n;
    while (p != (p & -p))
        p++;
    dp = (p << 1);
    int i;
    pair<int, int> t;
    mx.resize(dp);
    mn.resize(dp);
    wl.resize(dp);
    wr.resize(dp);
    for (i = p; i < dp; i++)
    {
        mx[i] = mn[i] = 0;
        wl[i] = i;
        wr[i] = i + 1;
    }
    for (i = p - 1; i > 0; i--)
    {
        mx[i] = mn[i] = 0;
        wl[i] = wl[i << 1];
        wr[i] = wr[(i << 1) ^ 1];
    }
    for (i = 0; i < k; i++)
    {
        if (op[i] == 1)
            upd(left[i] + p, right[i] + p + 1, 1, height[i], r);
        else
            upd(left[i] + p, right[i] + p + 1, 1, 0, height[i]);
    }
    for (i = 1; i < p; i++)
        push(i);
    for (i = 0; i < n; i++)
        finalHeight[i] = mx[i + p];
    return;
}

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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1060 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 80 ms 8144 KB Output is correct
3 Correct 188 ms 4688 KB Output is correct
4 Correct 501 ms 12880 KB Output is correct
5 Correct 280 ms 13392 KB Output is correct
6 Correct 272 ms 13396 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 8160 KB Output is correct
9 Correct 177 ms 4692 KB Output is correct
10 Correct 497 ms 12804 KB Output is correct
11 Correct 284 ms 13328 KB Output is correct
12 Correct 290 ms 13216 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 82 ms 8244 KB Output is correct
15 Correct 40 ms 1884 KB Output is correct
16 Correct 623 ms 13220 KB Output is correct
17 Correct 276 ms 13204 KB Output is correct
18 Correct 273 ms 13092 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 2 ms 344 KB Output is correct
4 Correct 6 ms 1092 KB Output is correct
5 Correct 5 ms 1060 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 8224 KB Output is correct
9 Correct 175 ms 4688 KB Output is correct
10 Correct 543 ms 12816 KB Output is correct
11 Correct 276 ms 13432 KB Output is correct
12 Correct 274 ms 13316 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 85 ms 8272 KB Output is correct
15 Correct 33 ms 1976 KB Output is correct
16 Correct 624 ms 13136 KB Output is correct
17 Correct 287 ms 13136 KB Output is correct
18 Correct 270 ms 13136 KB Output is correct
19 Correct 699 ms 91832 KB Output is correct
20 Correct 636 ms 89348 KB Output is correct
21 Correct 645 ms 91988 KB Output is correct
22 Correct 709 ms 89428 KB Output is correct
23 Correct 685 ms 89524 KB Output is correct
24 Correct 932 ms 89428 KB Output is correct
25 Correct 690 ms 89312 KB Output is correct
26 Correct 660 ms 91984 KB Output is correct
27 Correct 656 ms 91972 KB Output is correct
28 Correct 695 ms 89316 KB Output is correct
29 Correct 671 ms 89424 KB Output is correct
30 Correct 669 ms 89428 KB Output is correct