oj.uz

Submission #770649

# Submission time Handle Problem Language Result Execution time Memory
770649 2023-07-01T15:06:23 Z hafo Wall (IOI14_wall) C++14
100 / 100
 788 ms 140040 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 mx, mn;
    }; 
    
    node st[4 * maxn];
    pa lz[4 * maxn];

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

    void fix(int id, int l, int r, int type) {
        if(type == 1) {
            maxi(st[id].mx, lz[id].fi);
            maxi(st[id].mn, lz[id].fi);
        } else {
            mini(st[id].mx, lz[id].se);
            mini(st[id].mn, 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) {
            if(st[id].mx == -oo) ans[l] = 0;
            else ans[l] = st[id].mx;
            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:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~
wall.cpp: In member function 'void ST::get(int, int, int)':
wall.cpp:93:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62856 KB Output is correct
2 Correct 24 ms 62976 KB Output is correct
3 Correct 24 ms 62988 KB Output is correct
4 Correct 29 ms 63460 KB Output is correct
5 Correct 27 ms 63400 KB Output is correct
6 Correct 27 ms 63444 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62896 KB Output is correct
2 Correct 137 ms 74724 KB Output is correct
3 Correct 231 ms 70664 KB Output is correct
4 Correct 609 ms 77084 KB Output is correct
5 Correct 322 ms 84368 KB Output is correct
6 Correct 317 ms 82816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 62932 KB Output is correct
2 Correct 25 ms 63072 KB Output is correct
3 Correct 24 ms 62960 KB Output is correct
4 Correct 29 ms 63464 KB Output is correct
5 Correct 32 ms 63436 KB Output is correct
6 Correct 29 ms 63436 KB Output is correct
7 Correct 23 ms 62908 KB Output is correct
8 Correct 134 ms 76484 KB Output is correct
9 Correct 268 ms 70648 KB Output is correct
10 Correct 603 ms 83404 KB Output is correct
11 Correct 323 ms 84400 KB Output is correct
12 Correct 350 ms 82844 KB Output is correct
13 Correct 28 ms 62852 KB Output is correct
14 Correct 141 ms 76540 KB Output is correct
15 Correct 73 ms 64584 KB Output is correct
16 Correct 774 ms 83596 KB Output is correct
17 Correct 326 ms 83048 KB Output is correct
18 Correct 325 ms 83136 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 25 ms 63048 KB Output is correct
3 Correct 24 ms 62916 KB Output is correct
4 Correct 30 ms 63444 KB Output is correct
5 Correct 28 ms 63396 KB Output is correct
6 Correct 28 ms 63448 KB Output is correct
7 Correct 24 ms 62932 KB Output is correct
8 Correct 136 ms 76652 KB Output is correct
9 Correct 228 ms 70632 KB Output is correct
10 Correct 607 ms 83340 KB Output is correct
11 Correct 325 ms 84428 KB Output is correct
12 Correct 341 ms 82920 KB Output is correct
13 Correct 24 ms 62872 KB Output is correct
14 Correct 140 ms 76584 KB Output is correct
15 Correct 62 ms 64628 KB Output is correct
16 Correct 764 ms 83660 KB Output is correct
17 Correct 327 ms 83096 KB Output is correct
18 Correct 345 ms 83016 KB Output is correct
19 Correct 748 ms 140040 KB Output is correct
20 Correct 734 ms 129228 KB Output is correct
21 Correct 739 ms 139924 KB Output is correct
22 Correct 730 ms 129268 KB Output is correct
23 Correct 788 ms 129356 KB Output is correct
24 Correct 767 ms 129372 KB Output is correct
25 Correct 745 ms 129292 KB Output is correct
26 Correct 746 ms 139932 KB Output is correct
27 Correct 736 ms 139920 KB Output is correct
28 Correct 735 ms 129476 KB Output is correct
29 Correct 744 ms 129296 KB Output is correct
30 Correct 734 ms 129264 KB Output is correct