oj.uz

Submission #941092

# Submission time Handle Problem Language Result Execution time Memory
941092 2024-03-08T06:49:12 Z Amirreza_Fakhri Wall (IOI14_wall) C++17
0 / 100
 117 ms 46892 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] = l;
    }
}

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);
//     return 0;
// }

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33116 KB Output is correct
2 Incorrect 9 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33112 KB Output is correct
2 Incorrect 117 ms 46892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33116 KB Output is correct
2 Incorrect 9 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33116 KB Output is correct
2 Incorrect 11 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -