oj.uz

Submission #729754

# Submission time Handle Problem Language Result Execution time Memory
729754 2023-04-24T13:22:53 Z becaido Wall (IOI14_wall) C++17
100 / 100
 520 ms 83604 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define lpos pos<<1
#define rpos pos<<1|1

const int SIZE = 2e6 + 5;
const int INF = (1ll << 31) - 1;

int mx[3 * SIZE], mn[3 * SIZE];

void add (int pos, int x) {
    if (mx[pos] == -1)
        mn[pos] = max (mn[pos], x);
    else if (x >= mx[pos])
        mn[pos] = x, mx[pos] = -1;
    else if (x >= mn[pos])
        mn[pos] = x;
}

void del (int pos, int x) {
    if (mx[pos] == -1)
        mn[pos] = min (mn[pos], x);
    else if (x <= mn[pos])
        mn[pos] = x, mx[pos] = -1;
    else if (x <= mx[pos])
        mx[pos] = x;
}

void push_down (int pos) {
    if (mx[pos] == -1) {
        mx[lpos] = mx[rpos] = -1;
        mn[lpos] = mn[rpos] = mn[pos];
        mx[pos] = INF, mn[pos] = 0;
    } else {
        if (mn[pos] != 0) {
            add (lpos, mn[pos]);
            add (rpos, mn[pos]);
        }
        if (mx[pos] != INF) {
            del (lpos, mx[pos]);
            del (rpos, mx[pos]);
        }
        mx[pos] = INF, mn[pos] = 0;
    }
}

void modify (int pos, int l, int r, int L, int R, int t, int h) {
    if (l == L && r == R) {
        if (t == 1)
            add (pos, h);
        else
            del (pos, h);
    } else {
        push_down (pos);
        int mid = (L + R) / 2;
        if (r <= mid)
            modify (lpos, l, r, L, mid, t, h);
        else if (l > mid)
            modify (rpos, l, r, mid + 1, R, t, h);
        else {
            modify (lpos, l, mid, L, mid, t, h);
            modify (rpos, mid + 1, r, mid + 1, R, t, h);
        }
    }
}

void dfs (int pos, int l, int r, int ans[]) {
    if (l == r)
        ans[l] = mn[pos];
    else {
        push_down (pos);
        int mid = (l + r) / 2;
        dfs (lpos, l, mid, ans);
        dfs (rpos, mid + 1, r, ans);
    }
}

void buildWall (int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
    fill (mx, mx + 3 * n + 1, INF);
    fill (mn, mn + 3 * n + 1, 0);
    for (int i = 0; i < k; i++)
        modify (1, l[i], r[i], 0, n - 1, op[i], h[i]);
    dfs (1, 0, n - 1, ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 134 ms 13948 KB Output is correct
3 Correct 151 ms 7992 KB Output is correct
4 Correct 412 ms 20764 KB Output is correct
5 Correct 202 ms 21724 KB Output is correct
6 Correct 198 ms 20168 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 130 ms 13876 KB Output is correct
9 Correct 162 ms 7944 KB Output is correct
10 Correct 437 ms 20628 KB Output is correct
11 Correct 202 ms 21764 KB Output is correct
12 Correct 198 ms 20228 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 137 ms 13888 KB Output is correct
15 Correct 22 ms 1924 KB Output is correct
16 Correct 346 ms 20904 KB Output is correct
17 Correct 196 ms 20300 KB Output is correct
18 Correct 214 ms 20348 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 135 ms 13924 KB Output is correct
9 Correct 156 ms 7952 KB Output is correct
10 Correct 403 ms 20692 KB Output is correct
11 Correct 200 ms 21740 KB Output is correct
12 Correct 196 ms 20116 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 132 ms 13856 KB Output is correct
15 Correct 22 ms 2024 KB Output is correct
16 Correct 344 ms 20864 KB Output is correct
17 Correct 209 ms 20316 KB Output is correct
18 Correct 203 ms 20284 KB Output is correct
19 Correct 495 ms 83572 KB Output is correct
20 Correct 497 ms 81152 KB Output is correct
21 Correct 491 ms 83556 KB Output is correct
22 Correct 520 ms 81172 KB Output is correct
23 Correct 492 ms 81124 KB Output is correct
24 Correct 495 ms 81160 KB Output is correct
25 Correct 490 ms 81116 KB Output is correct
26 Correct 496 ms 83604 KB Output is correct
27 Correct 520 ms 83596 KB Output is correct
28 Correct 495 ms 81100 KB Output is correct
29 Correct 497 ms 81128 KB Output is correct
30 Correct 491 ms 81100 KB Output is correct