oj.uz

Submission #374870

# Submission time Handle Problem Language Result Execution time Memory
374870 2021-03-08T11:47:55 Z Alex_tz307 Wall (IOI14_wall) C++17
100 / 100
 1171 ms 114700 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 364 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 161 ms 8172 KB Output is correct
3 Correct 224 ms 5228 KB Output is correct
4 Correct 701 ms 14648 KB Output is correct
5 Correct 349 ms 14700 KB Output is correct
6 Correct 269 ms 14700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 11 ms 1260 KB Output is correct
5 Correct 6 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 161 ms 8172 KB Output is correct
9 Correct 222 ms 5228 KB Output is correct
10 Correct 721 ms 14700 KB Output is correct
11 Correct 279 ms 14700 KB Output is correct
12 Correct 267 ms 14700 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 161 ms 8172 KB Output is correct
15 Correct 56 ms 2540 KB Output is correct
16 Correct 1171 ms 14828 KB Output is correct
17 Correct 277 ms 14700 KB Output is correct
18 Correct 275 ms 14820 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 11 ms 1260 KB Output is correct
5 Correct 6 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 161 ms 8172 KB Output is correct
9 Correct 219 ms 5228 KB Output is correct
10 Correct 719 ms 14700 KB Output is correct
11 Correct 275 ms 14700 KB Output is correct
12 Correct 272 ms 14700 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 163 ms 8172 KB Output is correct
15 Correct 57 ms 2412 KB Output is correct
16 Correct 1145 ms 14764 KB Output is correct
17 Correct 283 ms 14700 KB Output is correct
18 Correct 278 ms 14836 KB Output is correct
19 Correct 1049 ms 114540 KB Output is correct
20 Correct 1028 ms 114540 KB Output is correct
21 Correct 1031 ms 114540 KB Output is correct
22 Correct 1031 ms 114540 KB Output is correct
23 Correct 1014 ms 114668 KB Output is correct
24 Correct 1018 ms 114700 KB Output is correct
25 Correct 1029 ms 114540 KB Output is correct
26 Correct 1022 ms 114584 KB Output is correct
27 Correct 1039 ms 114540 KB Output is correct
28 Correct 1012 ms 114532 KB Output is correct
29 Correct 1027 ms 114668 KB Output is correct
30 Correct 1035 ms 114532 KB Output is correct