oj.uz

Submission #524742

# Submission time Handle Problem Language Result Execution time Memory
524742 2022-02-09T23:18:16 Z abdzag Wall (IOI14_wall) C++17
100 / 100
 1727 ms 224512 KB 
#include <bits/stdc++.h>

typedef long long ll;
const long long inf = 2e9;
using namespace std;

struct Node
{
    Node *l = 0, *r = 0;
    int lo, hi;
    int max_of_interval = inf, min_of_interval = -inf; // Allowed max and allowed min of intervals
    Node(int lo, int hi) : lo(lo), hi(hi)
    {
        if (lo + 1 < hi)
        {
            int mid = lo + (hi - lo) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
        }
    }
    ~Node()
    {
        delete l;
        delete r;
    }
    int query(int pos)
    {
        if (lo + 1 == hi)
            return min_of_interval == -inf ? 0 : min_of_interval;
        push();
        int mid = lo + (hi - lo) / 2;
        if (pos < mid)
            return l->query(pos);
        return r->query(pos);
    }
    void minimize(int L, int R, int X)
    {
        if (R <= lo || hi <= L)
            return;
        if (L <= lo && hi <= R)
        {
            max_of_interval = min(X, max_of_interval);
            min_of_interval = min(X, min_of_interval);
            return;
        }
        push();
        l->minimize(L, R, X);
        r->minimize(L, R, X);
    }
    void maximize(int L, int R, int X)
    {
        if (R <= lo || hi <= L)
            return;
        if (L <= lo && hi <= R)
        {
            min_of_interval = max(X, min_of_interval);
            max_of_interval = max(max_of_interval, min_of_interval);
            return;
        }
        push();
        l->maximize(L, R, X);
        r->maximize(L, R, X);
    }
    void push()
    {

        l->minimize(lo, hi, max_of_interval);
        r->minimize(lo, hi, max_of_interval);
        l->maximize(lo, hi, min_of_interval);
        r->maximize(lo, hi, min_of_interval);
        max_of_interval=inf;
        min_of_interval=-inf;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Node *tree = new Node(0, n);
    for (int i = 0; i < k; i++)
    {
        ll l, r, a, type;
        type = op[i];
        l = left[i];
        r = right[i];
        a = height[i];
        r++;
        type--;
        if (type)
            tree->minimize(l, r, a);
        else
            tree->maximize(l, r, a);
    }
    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = tree->query(i);
    }
    delete tree;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 9 ms 1484 KB Output is correct
5 Correct 8 ms 1484 KB Output is correct
6 Correct 9 ms 1432 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 127 ms 8004 KB Output is correct
3 Correct 198 ms 5304 KB Output is correct
4 Correct 603 ms 27684 KB Output is correct
5 Correct 350 ms 28740 KB Output is correct
6 Correct 344 ms 27108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 1436 KB Output is correct
5 Correct 8 ms 1432 KB Output is correct
6 Correct 9 ms 1436 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 143 ms 13816 KB Output is correct
9 Correct 185 ms 9084 KB Output is correct
10 Correct 615 ms 27680 KB Output is correct
11 Correct 354 ms 28784 KB Output is correct
12 Correct 336 ms 27092 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 134 ms 13984 KB Output is correct
15 Correct 36 ms 3080 KB Output is correct
16 Correct 619 ms 27892 KB Output is correct
17 Correct 340 ms 27276 KB Output is correct
18 Correct 338 ms 27372 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 1416 KB Output is correct
5 Correct 9 ms 1384 KB Output is correct
6 Correct 10 ms 1452 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 126 ms 13912 KB Output is correct
9 Correct 185 ms 9064 KB Output is correct
10 Correct 609 ms 27732 KB Output is correct
11 Correct 343 ms 28724 KB Output is correct
12 Correct 336 ms 27096 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 129 ms 13812 KB Output is correct
15 Correct 35 ms 3016 KB Output is correct
16 Correct 608 ms 27956 KB Output is correct
17 Correct 340 ms 27392 KB Output is correct
18 Correct 344 ms 27304 KB Output is correct
19 Correct 1721 ms 224472 KB Output is correct
20 Correct 1698 ms 222040 KB Output is correct
21 Correct 1716 ms 224512 KB Output is correct
22 Correct 1706 ms 221972 KB Output is correct
23 Correct 1714 ms 222136 KB Output is correct
24 Correct 1714 ms 221956 KB Output is correct
25 Correct 1711 ms 221908 KB Output is correct
26 Correct 1707 ms 224500 KB Output is correct
27 Correct 1707 ms 224452 KB Output is correct
28 Correct 1727 ms 221992 KB Output is correct
29 Correct 1697 ms 221952 KB Output is correct
30 Correct 1717 ms 221976 KB Output is correct