oj.uz

Submission #941117

# Submission time Handle Problem Language Result Execution time Memory
941117 2024-03-08T07:23:42 Z Amirreza_Fakhri Wall (IOI14_wall) C++17
100 / 100
 582 ms 92452 KB 
// In the name of the God

#include "wall.h"

#include <bits/stdc++.h>
// #define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e6+5;

int n, k, sl[maxn*4], sr[maxn*4], ans[maxn];

void relax(int id, int l, int r) {
    int ll = sl[id], rr = sr[id];
    if (max(l, ll) <= min(r, rr)) sl[id] = max(l, ll), sr[id] = min(r, rr);
    else {
        if (rr < l) sl[id] = sr[id] = l;
        else sl[id] = sr[id] = r;
    }
}

void upd(int o, int s, int e, int h, int l = 0, int r = n, int id = 1) {
    if (s <= l and r <= e) {
        if (o == 1) relax(id, h, inf);
        else relax(id, 0, h);
        return;
    }
    int mid = (l+r)/2;
    relax(id*2, sl[id], sr[id]), relax(id*2+1, sl[id], sr[id]);
    sl[id] = 0, sr[id] = inf;
    if (s < mid) upd(o, s, e, h, l, mid, id*2);
    if (e > mid) upd(o, s, e, h, mid, r, id*2+1);
}

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

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

// int32_t main() {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     // buildWall();
//     cin >> n >> k;
//     for (int i = 1; i < maxn*4; i++) sr[i] = inf;
//     for (int i = 0; i < k; i++) {
//         int a, b, c, d;cin >> a >> b >> c >> d;
//         upd(a, b, c+1, d);
//     }
//     get();
//     for (int i = 0; i < n; i++) cout << ans[i] << '\n';
//     return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33116 KB Output is correct
2 Correct 8 ms 33316 KB Output is correct
3 Correct 11 ms 33116 KB Output is correct
4 Correct 11 ms 33628 KB Output is correct
5 Correct 10 ms 33472 KB Output is correct
6 Correct 10 ms 33628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33112 KB Output is correct
2 Correct 137 ms 41024 KB Output is correct
3 Correct 133 ms 39348 KB Output is correct
4 Correct 373 ms 54704 KB Output is correct
5 Correct 241 ms 55404 KB Output is correct
6 Correct 209 ms 53952 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33112 KB Output is correct
2 Correct 8 ms 33116 KB Output is correct
3 Correct 7 ms 33332 KB Output is correct
4 Correct 15 ms 33452 KB Output is correct
5 Correct 15 ms 33628 KB Output is correct
6 Correct 10 ms 33624 KB Output is correct
7 Correct 9 ms 33116 KB Output is correct
8 Correct 117 ms 46724 KB Output is correct
9 Correct 129 ms 40528 KB Output is correct
10 Correct 358 ms 54352 KB Output is correct
11 Correct 238 ms 55328 KB Output is correct
12 Correct 229 ms 53976 KB Output is correct
13 Correct 7 ms 33212 KB Output is correct
14 Correct 132 ms 46740 KB Output is correct
15 Correct 35 ms 34544 KB Output is correct
16 Correct 508 ms 54788 KB Output is correct
17 Correct 242 ms 54156 KB Output is correct
18 Correct 238 ms 53980 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 33116 KB Output is correct
2 Correct 10 ms 33116 KB Output is correct
3 Correct 8 ms 33120 KB Output is correct
4 Correct 12 ms 33436 KB Output is correct
5 Correct 12 ms 33628 KB Output is correct
6 Correct 11 ms 33452 KB Output is correct
7 Correct 6 ms 33256 KB Output is correct
8 Correct 130 ms 46672 KB Output is correct
9 Correct 158 ms 40532 KB Output is correct
10 Correct 372 ms 54412 KB Output is correct
11 Correct 236 ms 55372 KB Output is correct
12 Correct 222 ms 53996 KB Output is correct
13 Correct 7 ms 33116 KB Output is correct
14 Correct 122 ms 46800 KB Output is correct
15 Correct 34 ms 34652 KB Output is correct
16 Correct 507 ms 54776 KB Output is correct
17 Correct 239 ms 54112 KB Output is correct
18 Correct 227 ms 54152 KB Output is correct
19 Correct 512 ms 92352 KB Output is correct
20 Correct 549 ms 89768 KB Output is correct
21 Correct 582 ms 92332 KB Output is correct
22 Correct 582 ms 89696 KB Output is correct
23 Correct 512 ms 89752 KB Output is correct
24 Correct 544 ms 89632 KB Output is correct
25 Correct 513 ms 89860 KB Output is correct
26 Correct 501 ms 92360 KB Output is correct
27 Correct 516 ms 92452 KB Output is correct
28 Correct 497 ms 89924 KB Output is correct
29 Correct 490 ms 89772 KB Output is correct
30 Correct 497 ms 89740 KB Output is correct