oj.uz

Submission #987520

# Submission time Handle Problem Language Result Execution time Memory
987520 2024-05-23T00:01:39 Z ThegeekKnight16 Wall (IOI14_wall) C++17
100 / 100
 1176 ms 130760 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MAXN = 2e6 + 10;
struct node
{
    int maxVal, minVal, lz;

    node(int MX = 0, int MN = 0, int LZ = -1) : maxVal(MX), minVal(MN), lz(LZ) {}

    node operator+ (node outro)
    {
        return node(max(maxVal, outro.maxVal), min(minVal, outro.minVal));
    }
};
array<node, 4*MAXN> seg;

void refresh(int pos, int ini, int fim)
{
    if (seg[pos].lz == -1) return;
    int x = seg[pos].lz; seg[pos].lz = -1;
    seg[pos].maxVal = seg[pos].minVal = x;

    if (ini == fim) return;
    int e = 2*pos, d = e+1;
    seg[e].lz = seg[d].lz = x;
}

void updateAdd(int pos, int ini, int fim, int p, int q, int val)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim || seg[pos].minVal >= val) return;
    if (p <= ini && fim <= q && seg[pos].maxVal <= val)
    {
        seg[pos].lz = val;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    updateAdd(e, ini, m, p, q, val);
    updateAdd(d, m+1, fim, p, q, val);
    seg[pos] = seg[e] + seg[d];
}

void updateRem(int pos, int ini, int fim, int p, int q, int val)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim || seg[pos].maxVal <= val) return;
    if (p <= ini && fim <= q && seg[pos].minVal >= val)
    {
        seg[pos].lz = val;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    updateRem(e, ini, m, p, q, val);
    updateRem(d, m+1, fim, p, q, val);
    seg[pos] = seg[e] + seg[d];
}

node query(int pos, int ini, int fim, int p, int q)
{
    refresh(pos, ini, fim);
    if (q < ini || p > fim) return node(0, (int)1e9);
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    int e = 2*pos, d = e+1;
    return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i = 0; i < k; i++)
    {
        if (op[i] == 1) updateAdd(1, 0, n-1, left[i], right[i], height[i]);
        else updateRem(1, 0, n-1, left[i], right[i], height[i]);
    }

    for (int i = 0; i < n; i++) finalHeight[i] = query(1, 0, n-1, i, i).maxVal;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94296 KB Output is correct
2 Correct 34 ms 94300 KB Output is correct
3 Correct 32 ms 94436 KB Output is correct
4 Correct 36 ms 94548 KB Output is correct
5 Correct 37 ms 94544 KB Output is correct
6 Correct 36 ms 94804 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 94324 KB Output is correct
2 Correct 130 ms 107860 KB Output is correct
3 Correct 87 ms 100180 KB Output is correct
4 Correct 194 ms 112392 KB Output is correct
5 Correct 197 ms 113288 KB Output is correct
6 Correct 213 ms 111700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 94548 KB Output is correct
2 Correct 34 ms 94552 KB Output is correct
3 Correct 33 ms 94292 KB Output is correct
4 Correct 37 ms 94544 KB Output is correct
5 Correct 37 ms 94552 KB Output is correct
6 Correct 37 ms 94556 KB Output is correct
7 Correct 32 ms 94300 KB Output is correct
8 Correct 133 ms 107860 KB Output is correct
9 Correct 86 ms 101456 KB Output is correct
10 Correct 189 ms 112464 KB Output is correct
11 Correct 200 ms 113204 KB Output is correct
12 Correct 211 ms 111816 KB Output is correct
13 Correct 32 ms 94292 KB Output is correct
14 Correct 135 ms 107856 KB Output is correct
15 Correct 54 ms 95424 KB Output is correct
16 Correct 420 ms 112572 KB Output is correct
17 Correct 306 ms 111868 KB Output is correct
18 Correct 286 ms 111992 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 94292 KB Output is correct
2 Correct 32 ms 94480 KB Output is correct
3 Correct 31 ms 94300 KB Output is correct
4 Correct 37 ms 94544 KB Output is correct
5 Correct 37 ms 94556 KB Output is correct
6 Correct 38 ms 94356 KB Output is correct
7 Correct 31 ms 94288 KB Output is correct
8 Correct 131 ms 107840 KB Output is correct
9 Correct 87 ms 101456 KB Output is correct
10 Correct 190 ms 112212 KB Output is correct
11 Correct 196 ms 113364 KB Output is correct
12 Correct 245 ms 111700 KB Output is correct
13 Correct 36 ms 94292 KB Output is correct
14 Correct 153 ms 107824 KB Output is correct
15 Correct 56 ms 95312 KB Output is correct
16 Correct 421 ms 112424 KB Output is correct
17 Correct 284 ms 112052 KB Output is correct
18 Correct 284 ms 111996 KB Output is correct
19 Correct 1136 ms 130640 KB Output is correct
20 Correct 1175 ms 128388 KB Output is correct
21 Correct 1142 ms 130760 KB Output is correct
22 Correct 1145 ms 128260 KB Output is correct
23 Correct 1132 ms 128248 KB Output is correct
24 Correct 1176 ms 128088 KB Output is correct
25 Correct 1130 ms 128340 KB Output is correct
26 Correct 1144 ms 130548 KB Output is correct
27 Correct 1143 ms 130644 KB Output is correct
28 Correct 1130 ms 128280 KB Output is correct
29 Correct 1128 ms 128248 KB Output is correct
30 Correct 1160 ms 128588 KB Output is correct