oj.uz

Submission #939278

# Submission time Handle Problem Language Result Execution time Memory
939278 2024-03-06T08:06:14 Z a_l_i_r_e_z_a Wall (IOI14_wall) C++17
100 / 100
 604 ms 107432 KB 
// In the name of God
// Hope is last to die
 
#include <bits/stdc++.h>
using namespace std;
 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
 
const int maxn = 2e6 + 5;
const int inf = 1e5;
struct D{
    int mn, mx;
    D(){
        mn = 0;
        mx = inf;
    }
} node[maxn * 4];
int n, k, ans[maxn];

void change(int id, D d){
    if(d.mn >= node[id].mx) node[id].mn = node[id].mx = d.mn;
    else if(d.mx <= node[id].mn) node[id].mn = node[id].mx = d.mx;
    else{
        smax(node[id].mn, d.mn);
        smin(node[id].mx, d.mx);
    }
}

void relax(int id){
    change(id * 2, node[id]);
    change(id * 2 + 1, node[id]);
    node[id].mn = 0;
    node[id].mx = inf;
}

void upd(int s, int e, int ty, int h, int l = 0, int r = n, int id = 1){
    if(s <= l && r <= e){
        if(ty == 1){
            if(h >= node[id].mx) node[id].mn = node[id].mx = h;
            else smax(node[id].mn, h);
        }
        else{
            if(h <= node[id].mn) node[id].mn = node[id].mx = h;
            else smin(node[id].mx, h);
        }
        return;
    }
    if(e <= l || r <= s) return;
    relax(id);
    int mid = (l + r) / 2;
    upd(s, e, ty, h, l, mid, id * 2);
    upd(s, e, ty, h, mid, r, id * 2 + 1);
}

void get(int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        ans[l] = node[id].mn;
        return;
    }
    relax(id);
    int mid = (l + r) / 2;
    get(l, mid, id * 2);
    get(mid, r, id * 2 + 1);
}

// int32_t main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     cin >> n >> k;
//     while(k--){
//         int l, r, ty, h; cin >> ty >> l >> r >> h;
//         r++;
//         upd(l, r, ty, h);
//     }
//     get();
//     for(int i = 0; i < n; i++) cout << ans[i] << ' ';

//     return 0;
// }


void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    k = K;
    for(int i = 0; i < k; i++) upd(left[i], right[i] + 1, op[i], height[i]);
    get();
    for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64468 KB Output is correct
2 Correct 13 ms 64600 KB Output is correct
3 Correct 15 ms 64756 KB Output is correct
4 Correct 16 ms 64856 KB Output is correct
5 Correct 15 ms 64604 KB Output is correct
6 Correct 17 ms 64856 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 64348 KB Output is correct
2 Correct 114 ms 78164 KB Output is correct
3 Correct 124 ms 70456 KB Output is correct
4 Correct 322 ms 84804 KB Output is correct
5 Correct 251 ms 85912 KB Output is correct
6 Correct 226 ms 84048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64344 KB Output is correct
2 Correct 13 ms 64600 KB Output is correct
3 Correct 13 ms 64604 KB Output is correct
4 Correct 17 ms 64604 KB Output is correct
5 Correct 18 ms 64600 KB Output is correct
6 Correct 15 ms 64604 KB Output is correct
7 Correct 14 ms 64348 KB Output is correct
8 Correct 113 ms 78164 KB Output is correct
9 Correct 123 ms 71764 KB Output is correct
10 Correct 369 ms 84628 KB Output is correct
11 Correct 227 ms 85840 KB Output is correct
12 Correct 238 ms 84240 KB Output is correct
13 Correct 12 ms 64344 KB Output is correct
14 Correct 115 ms 78160 KB Output is correct
15 Correct 35 ms 65764 KB Output is correct
16 Correct 427 ms 85064 KB Output is correct
17 Correct 228 ms 84308 KB Output is correct
18 Correct 228 ms 84304 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64344 KB Output is correct
2 Correct 13 ms 64460 KB Output is correct
3 Correct 13 ms 64608 KB Output is correct
4 Correct 16 ms 64856 KB Output is correct
5 Correct 15 ms 64816 KB Output is correct
6 Correct 15 ms 64604 KB Output is correct
7 Correct 13 ms 64344 KB Output is correct
8 Correct 109 ms 78164 KB Output is correct
9 Correct 121 ms 71600 KB Output is correct
10 Correct 332 ms 84816 KB Output is correct
11 Correct 220 ms 85820 KB Output is correct
12 Correct 216 ms 84044 KB Output is correct
13 Correct 13 ms 64344 KB Output is correct
14 Correct 117 ms 78108 KB Output is correct
15 Correct 35 ms 65620 KB Output is correct
16 Correct 423 ms 85260 KB Output is correct
17 Correct 224 ms 84476 KB Output is correct
18 Correct 225 ms 84412 KB Output is correct
19 Correct 499 ms 107432 KB Output is correct
20 Correct 488 ms 104696 KB Output is correct
21 Correct 509 ms 107132 KB Output is correct
22 Correct 498 ms 104572 KB Output is correct
23 Correct 604 ms 104660 KB Output is correct
24 Correct 482 ms 104676 KB Output is correct
25 Correct 484 ms 104576 KB Output is correct
26 Correct 526 ms 107088 KB Output is correct
27 Correct 490 ms 107148 KB Output is correct
28 Correct 541 ms 104528 KB Output is correct
29 Correct 510 ms 104788 KB Output is correct
30 Correct 492 ms 104580 KB Output is correct