oj.uz

Submission #842255

# Submission time Handle Problem Language Result Execution time Memory
842255 2023-09-02T16:17:09 Z WongHokFong_cpp Wall (IOI14_wall) C++14
100 / 100
 618 ms 82028 KB 
#include "wall.h"
#include <cstdio>
using namespace std;
struct SMT
{
    int mx, mi;
    bool amx, ami;
} T[8000010];
int max(int x, int y)
{
    return x > y ? x : y;
}
int min(int x, int y)
{
    return x < y ? x : y;
}
void build(int k, int l, int r)
{
    if (l == r)
    {
        T[k].mx = 0;
        T[k].mi = 0;
        T[k].amx = 1;
        T[k].ami = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k * 2, l, mid);
    build(k * 2 + 1, mid + 1, r);
    T[k].amx = T[k].ami = 0;
    return;
}
void pushdown(int k)
{
    if (T[k].amx)
    {
        if (T[k * 2].amx)
            T[k * 2].mx = max(T[k * 2].mx, T[k].mx);
        else
            T[k * 2].amx = 1, T[k * 2].mx = T[k].mx;
        if (T[k * 2].ami)
            T[k * 2].mi = max(T[k].mx, T[k * 2].mi);
        if (T[k * 2 + 1].amx)
            T[k * 2 + 1].mx = max(T[k * 2 + 1].mx, T[k].mx);
        else
            T[k * 2 + 1].amx = 1, T[k * 2 + 1].mx = T[k].mx;
        if (T[k * 2 + 1].ami)
            T[k * 2 + 1].mi = max(T[k].mx, T[k * 2 + 1].mi);
    }
    if (T[k].ami)
    {
        if (T[k * 2].ami)
            T[k * 2].mi = min(T[k].mi, T[k * 2].mi);
        else
            T[k * 2].ami = 1, T[k * 2].mi = T[k].mi;
        if (T[k * 2].amx)
            T[k * 2].mx = min(T[k].mi, T[k * 2].mx);
        if (T[k * 2 + 1].ami)
            T[k * 2 + 1].mi = min(T[k].mi, T[k * 2 + 1].mi);
        else
            T[k * 2 + 1].ami = 1, T[k * 2 + 1].mi = T[k].mi;
        if (T[k * 2 + 1].amx)
            T[k * 2 + 1].mx = min(T[k].mi, T[k * 2 + 1].mx);
    }
    T[k].mx = 0;
    T[k].amx = 0;
    T[k].mi = 0;
    T[k].ami = 0;
}
void adding(int k, int l, int r, int x, int y, int height)
{
    if (x <= l && r <= y)
    {
        if (T[k].amx)
            T[k].mx = max(height, T[k].mx);
        else
            T[k].amx = 1, T[k].mx = height;
        if (T[k].ami)
            T[k].mi = max(height, T[k].mi);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(k);
    if (x <= mid)
        adding(k * 2, l, mid, x, y, height);
    if (mid + 1 <= y)
        adding(k * 2 + 1, mid + 1, r, x, y, height);
}
void removing(int k, int l, int r, int x, int y, int height)
{
    if (x <= l && r <= y)
    {
        if (T[k].ami)
            T[k].mi = min(height, T[k].mi);
        else
            T[k].ami = 1, T[k].mi = height;
        if (T[k].amx)
            T[k].mx = min(height, T[k].mx);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(k);
    if (x <= mid)
        removing(k * 2, l, mid, x, y, height);
    if (mid + 1 <= y)
        removing(k * 2 + 1, mid + 1, r, x, y, height);
}
int query(int k, int l, int r, int x)
{
    if (l == r && l == x)
    {
        return T[k].mx;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if (x <= mid)
        return query(k * 2, l, mid, x);
    else
        return query(k * 2 + 1, mid + 1, r, x);
}
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++)
    {
        if (op[i] == 1)
            adding(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
        else
            removing(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
    }
    for (int i = 1; i <= n; i++)
        finalHeight[i - 1] = query(1, 1, n, i);
    return;
}
/*
int n, k, op[500010], left[500010], right[500010], height[2000010], finalHeight[2000010];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i++)
    {
        scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", finalHeight[i]);
    }
}
*/

Subtask #1
8.0 / 8.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 2 ms 344 KB Output is correct
4 Correct 7 ms 1016 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 99 ms 11100 KB Output is correct
3 Correct 144 ms 6424 KB Output is correct
4 Correct 423 ms 17080 KB Output is correct
5 Correct 196 ms 17728 KB Output is correct
6 Correct 179 ms 17084 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 2 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 102 ms 11092 KB Output is correct
9 Correct 148 ms 6556 KB Output is correct
10 Correct 431 ms 17060 KB Output is correct
11 Correct 195 ms 18028 KB Output is correct
12 Correct 182 ms 16976 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 101 ms 11092 KB Output is correct
15 Correct 31 ms 2244 KB Output is correct
16 Correct 505 ms 17204 KB Output is correct
17 Correct 185 ms 16952 KB Output is correct
18 Correct 186 ms 17012 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 572 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 7 ms 860 KB Output is correct
5 Correct 4 ms 888 KB Output is correct
6 Correct 4 ms 1072 KB Output is correct
7 Correct 0 ms 428 KB Output is correct
8 Correct 101 ms 11092 KB Output is correct
9 Correct 150 ms 6556 KB Output is correct
10 Correct 418 ms 17044 KB Output is correct
11 Correct 193 ms 18108 KB Output is correct
12 Correct 183 ms 16920 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 102 ms 11116 KB Output is correct
15 Correct 30 ms 2384 KB Output is correct
16 Correct 509 ms 17352 KB Output is correct
17 Correct 188 ms 17028 KB Output is correct
18 Correct 191 ms 17232 KB Output is correct
19 Correct 596 ms 81996 KB Output is correct
20 Correct 590 ms 79448 KB Output is correct
21 Correct 606 ms 81944 KB Output is correct
22 Correct 593 ms 79444 KB Output is correct
23 Correct 586 ms 79604 KB Output is correct
24 Correct 618 ms 79444 KB Output is correct
25 Correct 587 ms 79396 KB Output is correct
26 Correct 595 ms 82004 KB Output is correct
27 Correct 594 ms 82028 KB Output is correct
28 Correct 595 ms 79440 KB Output is correct
29 Correct 601 ms 79588 KB Output is correct
30 Correct 599 ms 79844 KB Output is correct