Submission #941092

#	Time	Username	Problem	Language	Result	Execution time	Memory
941092		Amirreza_Fakhri	Wall (IOI14_wall)	C++17	0 / 100	117 ms	46892 KiB

wall

// 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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39