oj.uz

Submission #1091605

# Submission time Handle Problem Language Result Execution time Memory
1091605 2024-09-21T14:16:04 Z vladilius Wall (IOI14_wall) C++17
100 / 100
 953 ms 99408 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e5;

vector<pii> t;

void ap1(int v, int& x){
    t[v].ff = max(t[v].ff, x);
    if (t[v].ff > t[v].ss) t[v].ss = t[v].ff;
}

void ap2(int v, int& x){
    t[v].ss = min(t[v].ss, x);
    if (t[v].ff > t[v].ss) t[v].ff = t[v].ss;
}

void push(int& v){
    int vv = 2 * v;
    ap1(vv, t[v].ff);
    ap1(vv + 1, t[v].ff);
    ap2(vv, t[v].ss);
    ap2(vv + 1, t[v].ss);
    t[v] = {0, inf};
}

void chmax(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap1(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmax(vv, tl, tm, l, r, x);
    chmax(vv + 1, tm + 1, tr, l, r, x);
}

void chmin(int v, int tl, int tr, int& l, int& r, int& x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ap2(v, x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    chmin(vv, tl, tm, l, r, x);
    chmin(vv + 1, tm + 1, tr, l, r, x);
}

int f(int x, pii& d){
    return min(max(x, d.ff), d.ss);
}

void get(int v, int tl, int tr, int p, int& x){
    x = f(x, t[v]);
    if (tl == tr) return;
    int tm = (tl + tr) / 2, vv = 2 * v;
    push(v);
    if (p <= tm){
        get(vv, tl, tm, p, x);
    }
    else {
        get(vv + 1, tm + 1, tr, p, x);
    }
}

void buildWall(int n, int k, int type[], int l[], int r[], int h[], int H[]){
    t.assign(4 * n, {0, inf});
    for (int i = 0; i < k; i++){
        l[i]++; r[i]++;
        if (type[i] == 1){
            chmax(1, 1, n, l[i], r[i], h[i]);
        }
        else {
            chmin(1, 1, n, l[i], r[i], h[i]);
        }
    }
    
    for (int i = 0; i < n; i++) get(1, 1, n, i + 1, H[i]);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 6 ms 960 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 856 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 88 ms 13932 KB Output is correct
3 Correct 122 ms 8016 KB Output is correct
4 Correct 364 ms 21568 KB Output is correct
5 Correct 242 ms 22464 KB Output is correct
6 Correct 217 ms 21072 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 87 ms 13908 KB Output is correct
9 Correct 130 ms 8020 KB Output is correct
10 Correct 370 ms 21396 KB Output is correct
11 Correct 233 ms 22524 KB Output is correct
12 Correct 248 ms 21076 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 88 ms 13912 KB Output is correct
15 Correct 28 ms 1976 KB Output is correct
16 Correct 490 ms 21840 KB Output is correct
17 Correct 247 ms 21072 KB Output is correct
18 Correct 250 ms 21072 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 91 ms 14064 KB Output is correct
9 Correct 123 ms 8148 KB Output is correct
10 Correct 361 ms 21588 KB Output is correct
11 Correct 248 ms 22608 KB Output is correct
12 Correct 227 ms 20896 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 94 ms 13884 KB Output is correct
15 Correct 27 ms 2140 KB Output is correct
16 Correct 475 ms 21680 KB Output is correct
17 Correct 238 ms 21072 KB Output is correct
18 Correct 250 ms 21192 KB Output is correct
19 Correct 936 ms 99408 KB Output is correct
20 Correct 866 ms 96832 KB Output is correct
21 Correct 906 ms 99264 KB Output is correct
22 Correct 864 ms 96848 KB Output is correct
23 Correct 915 ms 96960 KB Output is correct
24 Correct 942 ms 96800 KB Output is correct
25 Correct 871 ms 96716 KB Output is correct
26 Correct 923 ms 99264 KB Output is correct
27 Correct 953 ms 99256 KB Output is correct
28 Correct 901 ms 96696 KB Output is correct
29 Correct 882 ms 96824 KB Output is correct
30 Correct 898 ms 96964 KB Output is correct