oj.uz

Submission #1006118

# Submission time Handle Problem Language Result Execution time Memory
1006118 2024-06-23T12:31:55 Z c2zi6 Wall (IOI14_wall) C++14
100 / 100
 502 ms 100540 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "wall.h"

PII perform(PII a, PII b) {
    PII ret = {max(a.ff, b.ff), min(a.ss, b.ss)};
    if (ret.ff > ret.ss) {
        if (b.ff > a.ss) return {b.ff, b.ff};
        return {b.ss, b.ss};
    }
    return ret;
}
struct SEGTREE {
    int n;
    VPI tree;
    VPI lazy;
    SEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = VPI(2*n, {0, +1e9});
        lazy = VPI(2*n, {0, +1e9});
    }
    void push(int N) {
        if (N < n-1) {
            lazy[2*N+1] = perform(lazy[2*N+1], lazy[N]);
            lazy[2*N+2] = perform(lazy[2*N+2], lazy[N]);
        } else {
            tree[N] = perform(tree[N], lazy[N]);
        }
        lazy[N] = {0, +1e9};
    }
    void setmx(int N, int L, int R, int l, int r, int h) {
        push(N);
        if (R < l || L > r) return;
        if (l <= L && R <= r) {
            lazy[N] = {0, h};
            push(N);
            return;
        }
        int M = (L+R)/2;
        setmx(2*N+1, L, M, l, r, h);
        setmx(2*N+2, M+1, R, l, r, h);
    }
    void setmn(int N, int L, int R, int l, int r, int h) {
        push(N);
        if (R < l || L > r) return;
        if (l <= L && R <= r) {
            lazy[N] = {h, +1e9};
            push(N);
            return;
        }
        int M = (L+R)/2;
        setmn(2*N+1, L, M, l, r, h);
        setmn(2*N+2, M+1, R, l, r, h);
    }
    void print(int N, int L, int R) {
        if (N > 2*n-2) return;
        cout << N << "," << L+1 << ".." << R+1 << ": " << lazy[N].ff << ".." << lazy[N].ss << endl;
        int M = (L+R)/2;
        print(2*N+1, L, M);
        print(2*N+2, M+1, R);
    }
    void print() {
        print(0, 0, n-1);
        replr(i, n-1, 2*n-2) {
            cout << tree[i].ff << ".." << tree[i].ss << endl;
        }
    }
    void finish(int N = 0) {
        if (N > 2*n-2) return;
        push(N);
        finish(2*N+1);
        finish(2*N+2);
    }
    VI verj() {
        VI ret;
        replr(i, n-1, 2*n-2) ret.pb(tree[i].ff);
        return ret;
    }
    void setmx(int l, int r, int h) {
        setmx(0, 0, n-1, l, r, h);
    }
    void setmn(int l, int r, int h) {
        setmn(0, 0, n-1, l, r, h);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SEGTREE seg(n);
    for (int i = 0; i < k; i++) {
        int l = left[i];
        int r = right[i];
        int h = height[i];
        /*l--, r--;*/
        if (op[i] == 1) seg.setmn(l, r, h);
        else seg.setmx(l, r, h);
        /*seg.print();*/
        /*cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAa" << endl;*/
    }
    seg.finish();
    VI ans = seg.verj();
    rep(i, n) finalHeight[i] = ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1168 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 5 ms 1328 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 13884 KB Output is correct
3 Correct 121 ms 8740 KB Output is correct
4 Correct 332 ms 23016 KB Output is correct
5 Correct 201 ms 23500 KB Output is correct
6 Correct 184 ms 21964 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 78 ms 14068 KB Output is correct
9 Correct 106 ms 8788 KB Output is correct
10 Correct 321 ms 22788 KB Output is correct
11 Correct 200 ms 23500 KB Output is correct
12 Correct 194 ms 21760 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 88 ms 13836 KB Output is correct
15 Correct 27 ms 2788 KB Output is correct
16 Correct 496 ms 22988 KB Output is correct
17 Correct 202 ms 22276 KB Output is correct
18 Correct 202 ms 22220 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 92 ms 13892 KB Output is correct
9 Correct 113 ms 8788 KB Output is correct
10 Correct 313 ms 22980 KB Output is correct
11 Correct 175 ms 23440 KB Output is correct
12 Correct 175 ms 21964 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 13860 KB Output is correct
15 Correct 27 ms 2644 KB Output is correct
16 Correct 502 ms 22824 KB Output is correct
17 Correct 200 ms 22220 KB Output is correct
18 Correct 194 ms 22396 KB Output is correct
19 Correct 498 ms 100364 KB Output is correct
20 Correct 457 ms 100340 KB Output is correct
21 Correct 467 ms 100540 KB Output is correct
22 Correct 448 ms 100536 KB Output is correct
23 Correct 451 ms 100540 KB Output is correct
24 Correct 442 ms 100540 KB Output is correct
25 Correct 469 ms 100504 KB Output is correct
26 Correct 451 ms 100540 KB Output is correct
27 Correct 465 ms 100540 KB Output is correct
28 Correct 447 ms 100540 KB Output is correct
29 Correct 452 ms 100540 KB Output is correct
30 Correct 477 ms 100436 KB Output is correct