oj.uz

Submission #374869

# Submission time Handle Problem Language Result Execution time Memory
374869 2021-03-08T11:46:30 Z Alex_tz307 Wall (IOI14_wall) C++17
100 / 100
 1223 ms 125164 KB 
#include <bits/stdc++.h>

using namespace std;

struct Segtree {
    int Size;
    vector<pair<int,int>> tree;
    vector<pair<bool,int>> lazy_min, lazy_max;

    void init(int N) {
        Size = 1;
        while(Size < N)
            Size <<= 1;
        tree.assign((Size << 1) + 1, make_pair(INT_MAX, 0));
        lazy_min.assign((Size << 1) + 1, make_pair(false, INT_MAX));
        lazy_max.assign((Size << 1) + 1, make_pair(false, 0));
    }

    void propagate(int x, int lx, int rx) {
        if(lx == rx)
            return;
        if(lazy_min[x].first) {
            tree[x << 1].first = min(tree[x << 1].first, lazy_min[x].second);
            tree[(x << 1) | 1].first = min(tree[(x << 1) | 1].first, lazy_min[x].second);
            tree[x << 1].second = min(tree[x << 1].first, tree[x << 1].second);
            tree[(x << 1) | 1].second = min(tree[(x << 1) | 1].first, tree[(x << 1) | 1].second);
            lazy_min[x << 1].first = lazy_min[(x << 1) | 1].first = true;
            lazy_min[x << 1].second = min(lazy_min[x << 1].second, lazy_min[x].second);
            lazy_min[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_min[x].second);
            if(lazy_max[x << 1].first)
                lazy_max[x << 1].second = min(lazy_min[x << 1].second, lazy_max[x << 1].second);
            if(lazy_max[(x << 1) | 1].first)
                lazy_max[(x << 1) | 1].second = min(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
            lazy_min[x] = make_pair(false, INT_MAX);
        }
        if(lazy_max[x].first) {
            tree[x << 1].second = max(tree[x << 1].second, lazy_max[x].second);
            tree[(x << 1) | 1].second = max(tree[(x << 1) | 1].second, lazy_max[x].second);
            tree[x << 1].first = max(tree[x << 1].first, tree[x << 1].second);
            tree[(x << 1) | 1].first = max(tree[(x << 1) | 1].first, tree[(x << 1) | 1].second);
            lazy_max[x << 1].first = lazy_max[(x << 1) | 1].first = true;
            lazy_max[x << 1].second = max(lazy_max[x << 1].second, lazy_max[x].second);
            lazy_max[(x << 1) | 1].second = max(lazy_max[(x << 1) | 1].second, lazy_max[x].second);
            if(lazy_min[x << 1].first)
                lazy_min[x << 1].second = max(lazy_min[x << 1].second, lazy_max[x << 1].second);
            if(lazy_min[(x << 1) | 1].first)
                lazy_min[(x << 1) | 1].second = max(lazy_min[(x << 1) | 1].second, lazy_max[(x << 1) | 1].second);
            lazy_max[x] = make_pair(false, 0);
        }
    }

    void maximize(int x, int lx, int rx, int st, int dr, int h) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            tree[x].second = max(tree[x].second, h);
            tree[x].first = max(tree[x].first, tree[x].second);
            lazy_max[x].first = true;
            lazy_max[x].second = max(lazy_max[x].second, h);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            maximize(x << 1, lx, mid, st, dr, h);
        if(mid < dr)
            maximize((x << 1) | 1, mid + 1, rx, st, dr, h);
    }

    void minimize(int x, int lx, int rx, int st, int dr, int h) {
        propagate(x, lx, rx);
        if(st <= lx && rx <= dr) {
            tree[x].first = min(tree[x].first, h);
            tree[x].second = min(tree[x].second, tree[x].first);
            lazy_min[x].first = true;
            lazy_min[x].second = min(lazy_min[x].second, h);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(st <= mid)
            minimize(x << 1, lx, mid, st, dr, h);
        if(mid < dr)
            minimize((x << 1) | 1, mid + 1, rx, st, dr, h);
    }

    int query(int x, int lx, int rx, int poz) {
        propagate(x, lx, rx);
        if(lx == rx)
            return tree[x].second;
        int mid = (lx + rx) >> 1;
        if(poz <= mid)
            return query(x << 1, lx, mid, poz);
        else
            return query((x << 1) | 1, mid + 1, rx, poz);
    }
};


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segtree tree;
    tree.init(n);
    for(int i = 0; i < k; ++i) 
        if(op[i] == 1)
            tree.maximize(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
        else
            tree.minimize(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
    for(int i = 0; i < n; ++i)
        finalHeight[i] = tree.query(1, 1, n, i + 1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 10 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 166 ms 13932 KB Output is correct
3 Correct 217 ms 9068 KB Output is correct
4 Correct 712 ms 24300 KB Output is correct
5 Correct 282 ms 24812 KB Output is correct
6 Correct 275 ms 23364 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 268 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 15 ms 1260 KB Output is correct
5 Correct 6 ms 1260 KB Output is correct
6 Correct 7 ms 1260 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 161 ms 14060 KB Output is correct
9 Correct 219 ms 8940 KB Output is correct
10 Correct 732 ms 24428 KB Output is correct
11 Correct 285 ms 24812 KB Output is correct
12 Correct 270 ms 23292 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 171 ms 14060 KB Output is correct
15 Correct 57 ms 2924 KB Output is correct
16 Correct 1223 ms 24372 KB Output is correct
17 Correct 288 ms 23788 KB Output is correct
18 Correct 289 ms 23788 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 11 ms 1260 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 160 ms 13932 KB Output is correct
9 Correct 213 ms 9068 KB Output is correct
10 Correct 757 ms 24500 KB Output is correct
11 Correct 282 ms 24812 KB Output is correct
12 Correct 274 ms 23404 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 164 ms 13932 KB Output is correct
15 Correct 55 ms 2924 KB Output is correct
16 Correct 1179 ms 24556 KB Output is correct
17 Correct 282 ms 23916 KB Output is correct
18 Correct 288 ms 23788 KB Output is correct
19 Correct 1036 ms 124960 KB Output is correct
20 Correct 1040 ms 125164 KB Output is correct
21 Correct 1037 ms 124908 KB Output is correct
22 Correct 1032 ms 125036 KB Output is correct
23 Correct 1052 ms 124996 KB Output is correct
24 Correct 1028 ms 125164 KB Output is correct
25 Correct 1026 ms 124908 KB Output is correct
26 Correct 1050 ms 125036 KB Output is correct
27 Correct 1054 ms 124908 KB Output is correct
28 Correct 1022 ms 125036 KB Output is correct
29 Correct 1022 ms 125036 KB Output is correct
30 Correct 1024 ms 124908 KB Output is correct