oj.uz

Submission #770652

# Submission time Handle Problem Language Result Execution time Memory
770652 2023-07-01T15:12:14 Z hafo Wall (IOI14_wall) C++14
100 / 100
 668 ms 113128 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e6 + 7;
const ll oo = 1e9 + 69;

int n, k, op[maxn], l[maxn], r[maxn], height[maxn], ans[maxn];

struct ST {
    struct node {
        int val;
    }; 
    
    node st[4 * maxn];
    pa lz[4 * maxn];

    void init() {
        for(int id = 1; id <= 4 * n; id++) {
            st[id].val = 0;
            lz[id] = {-oo, oo};
        }
    }

    void fix(int id, int l, int r, int type) {
        if(type == 1) {
            maxi(st[id].val, lz[id].fi);
        } else {
            mini(st[id].val, lz[id].se);
        }
        if(l != r) {
            if(type == 1) {
                maxi(lz[id << 1].fi, lz[id].fi);
                maxi(lz[id << 1].se, lz[id].fi);
                maxi(lz[id << 1 | 1].fi, lz[id].fi);
                maxi(lz[id << 1 | 1].se, lz[id].fi);
            } else {
                mini(lz[id << 1].fi, lz[id].se);
                mini(lz[id << 1].se, lz[id].se);
                mini(lz[id << 1 | 1].fi, lz[id].se);
                mini(lz[id << 1 | 1].se, lz[id].se);
            }
        }
        if(type == 1) lz[id].fi = -oo;
        else lz[id].se = oo;
    }

    void update(int id, int l, int r, int u, int v, int val, int type) {
        fix(id, l, r, 0);
        fix(id, l, r, 1);
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            if(type == 1) {
                maxi(lz[id].fi, val);
                maxi(lz[id].se, val);
            } else {
                mini(lz[id].fi, val);
                mini(lz[id].se, val);
            }
            fix(id, l, r, type);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v, val, type);
        update(id << 1 | 1, mid + 1, r, u, v, val, type);
    }

    void get(int id, int l, int r) {
        fix(id, l, r, 0);
        fix(id, l, r, 1);
        if(l == r) {
            ans[l] = st[id].val;
            return;
        }
        int mid = l + r >> 1;
        get(id << 1, l, mid);
        get(id << 1 | 1, mid + 1, r);
    }
} st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    st.init();
    for(int i = 0; i < k; i++) {
        st.update(1, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);
    }
    st.get(1, 1, n);
    for(int i = 0; i < n; i++) {
        finalHeight[i] = ans[i + 1];
    }
}

Compilation message

wall.cpp: In member function 'void ST::update(int, int, int, int, int, int, int)':
wall.cpp:77:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int mid = l + r >> 1;
      |                   ~~^~~
wall.cpp: In member function 'void ST::get(int, int, int)':
wall.cpp:89:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62932 KB Output is correct
2 Correct 22 ms 62944 KB Output is correct
3 Correct 23 ms 62972 KB Output is correct
4 Correct 28 ms 63200 KB Output is correct
5 Correct 28 ms 63188 KB Output is correct
6 Correct 27 ms 63180 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 62932 KB Output is correct
2 Correct 134 ms 70720 KB Output is correct
3 Correct 207 ms 66644 KB Output is correct
4 Correct 570 ms 72692 KB Output is correct
5 Correct 284 ms 73276 KB Output is correct
6 Correct 291 ms 73240 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62892 KB Output is correct
2 Correct 22 ms 62988 KB Output is correct
3 Correct 22 ms 62960 KB Output is correct
4 Correct 28 ms 63332 KB Output is correct
5 Correct 26 ms 63248 KB Output is correct
6 Correct 26 ms 63228 KB Output is correct
7 Correct 24 ms 62932 KB Output is correct
8 Correct 135 ms 70664 KB Output is correct
9 Correct 208 ms 66632 KB Output is correct
10 Correct 590 ms 72744 KB Output is correct
11 Correct 285 ms 73168 KB Output is correct
12 Correct 286 ms 73204 KB Output is correct
13 Correct 27 ms 62932 KB Output is correct
14 Correct 177 ms 70708 KB Output is correct
15 Correct 58 ms 63764 KB Output is correct
16 Correct 668 ms 72976 KB Output is correct
17 Correct 301 ms 73024 KB Output is correct
18 Correct 295 ms 72920 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62932 KB Output is correct
2 Correct 24 ms 62964 KB Output is correct
3 Correct 23 ms 62900 KB Output is correct
4 Correct 30 ms 63184 KB Output is correct
5 Correct 26 ms 63208 KB Output is correct
6 Correct 27 ms 63172 KB Output is correct
7 Correct 23 ms 62900 KB Output is correct
8 Correct 155 ms 70768 KB Output is correct
9 Correct 210 ms 66636 KB Output is correct
10 Correct 550 ms 72688 KB Output is correct
11 Correct 289 ms 73240 KB Output is correct
12 Correct 280 ms 73252 KB Output is correct
13 Correct 22 ms 62860 KB Output is correct
14 Correct 147 ms 70712 KB Output is correct
15 Correct 57 ms 63876 KB Output is correct
16 Correct 668 ms 73008 KB Output is correct
17 Correct 298 ms 72980 KB Output is correct
18 Correct 294 ms 72948 KB Output is correct
19 Correct 647 ms 113048 KB Output is correct
20 Correct 641 ms 106572 KB Output is correct
21 Correct 642 ms 113128 KB Output is correct
22 Correct 629 ms 106508 KB Output is correct
23 Correct 639 ms 106520 KB Output is correct
24 Correct 638 ms 106548 KB Output is correct
25 Correct 630 ms 106492 KB Output is correct
26 Correct 644 ms 113056 KB Output is correct
27 Correct 633 ms 113116 KB Output is correct
28 Correct 639 ms 106528 KB Output is correct
29 Correct 627 ms 106460 KB Output is correct
30 Correct 634 ms 106480 KB Output is correct