oj.uz

Submission #626106

# Submission time Handle Problem Language Result Execution time Memory
626106 2022-08-11T08:30:45 Z Duy_e Wall (IOI14_wall) C++14
100 / 100
 1061 ms 69536 KB 
#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e6 + 5;

struct node {
    int ma, mi;

    void init(int x, int y) {
        ma = x;
        mi = y;
    }

} st[4 * N];

void down(int id) {
    int u = id << 1, v = id << 1 | 1;

    int t = st[id].mi;
    if (t != -1) {
        st[u].mi = max(t, st[u].mi);
        st[u].ma = max(t, st[u].ma);
        st[v].mi = max(t, st[v].mi);
        st[v].ma = max(t, st[v].ma);
    }

    st[id].mi = 0;

    t = st[id].ma;
    if (t != -1) {
        // cout << id << ": " << t << '\n';
        st[u].ma = min(t, st[u].ma);
        st[u].mi = min(t, st[u].mi);
        st[v].ma = min(t, st[v].ma);
        st[v].mi = min(t, st[v].mi);
    }

    st[id].ma = 1e9;
}

ll get(int id, int l, int r, int i) {
    if (l == r) return id;

    down(id);

    int mid = l + r >> 1;
    if (mid >= i) return get(id << 1, l, mid, i);
    return get(id << 1 | 1, mid + 1, r, i);
}

void upd(int id, int l, int r, int lef, int rig, int t, int v) {
    if (l > rig || r < lef) return;
    if (lef <= l && r <= rig) {
        if (t == 1) { // adding phase
            st[id].mi = max(st[id].mi, v);
            st[id].ma = max(st[id].ma, v);
        } 

        if (t == 2) { // removing phase
            // cout << "v: " << st[id].ma << ' ' << v << '\n';
            st[id].ma = min(st[id].ma, v);
            st[id].mi = min(st[id].mi, v);
        }

        return;
    }

    if (r != l)
        down(id);
    int mid = l + r >> 1;
    upd(id << 1, l, mid, lef, rig, t, v);
    upd(id << 1 | 1, mid + 1, r, lef, rig, t, v);
}

void build(int id, int l, int r) {
    st[id].init(1e9, 0);
    if (l == r) return;

    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

ll ans(int id) {
    if (st[id].mi == -1) return st[id].ma;
    return st[id].mi;    
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]) {

    build(1, 0, n - 1);

    for (int i = 0; i < k; i ++)
        upd(1, 0, n - 1, left[i], right[i], op[i], height[i]);

    for (int i = 0; i < n; i ++)
        finalheight[i] = ans(get(1, 0, n - 1, i));

}

// ll n, k;
// int l[N], r[N], h[N], fh[N], op[N];

// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     #ifndef ONLINE_JUDGE
//         freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
//     #endif
    
//     cin >> n >> k;
//     for (int i = 0; i < k; i ++)
//         cin >> op[i] >> l[i] >> r[i] >> h[i];

//     buildWall(n, k, op, l, r, h, fh);

//     for (int i = 0; i < n; i ++)   
//         cout << fh[i] << '\n';

//     return 0;
// }

Compilation message

wall.cpp: In function 'long long int get(int, int, int, int)':
wall.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 6 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 131 ms 13924 KB Output is correct
3 Correct 154 ms 7912 KB Output is correct
4 Correct 402 ms 20376 KB Output is correct
5 Correct 270 ms 21400 KB Output is correct
6 Correct 271 ms 19820 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 368 KB Output is correct
4 Correct 6 ms 764 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 7 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 142 ms 13848 KB Output is correct
9 Correct 141 ms 7912 KB Output is correct
10 Correct 412 ms 20464 KB Output is correct
11 Correct 310 ms 21360 KB Output is correct
12 Correct 327 ms 19868 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 145 ms 13876 KB Output is correct
15 Correct 29 ms 1992 KB Output is correct
16 Correct 389 ms 20704 KB Output is correct
17 Correct 274 ms 20044 KB Output is correct
18 Correct 267 ms 19940 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 6 ms 832 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 764 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 142 ms 13900 KB Output is correct
9 Correct 143 ms 7916 KB Output is correct
10 Correct 383 ms 20352 KB Output is correct
11 Correct 286 ms 21492 KB Output is correct
12 Correct 298 ms 19808 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 129 ms 13896 KB Output is correct
15 Correct 25 ms 2000 KB Output is correct
16 Correct 383 ms 20648 KB Output is correct
17 Correct 274 ms 19996 KB Output is correct
18 Correct 275 ms 20000 KB Output is correct
19 Correct 973 ms 69412 KB Output is correct
20 Correct 990 ms 67032 KB Output is correct
21 Correct 1018 ms 69528 KB Output is correct
22 Correct 1010 ms 66996 KB Output is correct
23 Correct 987 ms 67016 KB Output is correct
24 Correct 1061 ms 67008 KB Output is correct
25 Correct 972 ms 66980 KB Output is correct
26 Correct 971 ms 69440 KB Output is correct
27 Correct 942 ms 69536 KB Output is correct
28 Correct 923 ms 67124 KB Output is correct
29 Correct 934 ms 67036 KB Output is correct
30 Correct 919 ms 66928 KB Output is correct