oj.uz

Submission #831588

# Submission time Handle Problem Language Result Execution time Memory
831588 2023-08-20T10:56:20 Z otarius Wall (IOI14_wall) C++17
100 / 100
 793 ms 114964 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#include <climits>
using namespace std;

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long

// #define int long long
// #define int unsigned long long

const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;

int n, k;
struct node {
    int mn = INT_MAX, mx = 0;
}; vector<node> lazy;
void modify(node &a, node b) {
    if (b.mn < a.mx) {
        a.mx = b.mn;
        a.mn = b.mn;
    } else if (b.mx > a.mn) {
        a.mx = b.mx;
        a.mn = b.mx;
    } else {
        a.mx = max(a.mx, b.mx);
        a.mn = min(a.mn, b.mn);
    }
}
void propagate(int v) {
    modify(lazy[2 * v], lazy[v]);
    modify(lazy[2 * v + 1], lazy[v]);
    lazy[v].mn = INT_MAX; lazy[v].mx = 0;
}
void update(int v, int tl, int tr, int l, int r, node u) {
    if (r < tl || tr < l)
        return;
    if (l <= tl && tr <= r) {
        modify(lazy[v], u);
        return;
    } if (tl != tr)
        propagate(v);
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, min(r, tm), u);
    update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, u);
}
void adding(int l, int r, int h) {
    node v = *new node();
    v.mx = h; v.mn = INT_MAX;
    update(1, 1, n, l, r, v);
}
void removing(int l, int r, int h) {
    node v = *new node();
    v.mn = h; v.mx = 0;
    update(1, 1, n, l, r, v);
}
int getval(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return lazy[v].mx;
    propagate(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) return getval(2 * v, tl, tm, pos);
    else return getval(2 * v + 1, tm + 1, tr, pos);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    n = N; k = K;
    lazy.resize(4 * n);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) adding(left[i] + 1, right[i] + 1, height[i]);
        else removing(left[i] + 1, right[i] + 1, height[i]);
    } for (int i = 0; i < n; i++)
        finalHeight[i] = getval(1, 1, n, i + 1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 1008 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 122 ms 29564 KB Output is correct
3 Correct 127 ms 14448 KB Output is correct
4 Correct 362 ms 37024 KB Output is correct
5 Correct 251 ms 38060 KB Output is correct
6 Correct 231 ms 36468 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 6 ms 980 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 120 ms 29540 KB Output is correct
9 Correct 128 ms 14416 KB Output is correct
10 Correct 360 ms 37060 KB Output is correct
11 Correct 230 ms 38072 KB Output is correct
12 Correct 231 ms 36496 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 123 ms 29564 KB Output is correct
15 Correct 28 ms 2928 KB Output is correct
16 Correct 455 ms 37340 KB Output is correct
17 Correct 238 ms 36696 KB Output is correct
18 Correct 239 ms 36776 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 1008 KB Output is correct
5 Correct 5 ms 948 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 120 ms 29556 KB Output is correct
9 Correct 156 ms 14448 KB Output is correct
10 Correct 352 ms 37008 KB Output is correct
11 Correct 239 ms 38072 KB Output is correct
12 Correct 233 ms 36600 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 127 ms 29708 KB Output is correct
15 Correct 27 ms 2892 KB Output is correct
16 Correct 463 ms 37260 KB Output is correct
17 Correct 246 ms 36668 KB Output is correct
18 Correct 240 ms 36660 KB Output is correct
19 Correct 759 ms 114928 KB Output is correct
20 Correct 747 ms 112428 KB Output is correct
21 Correct 735 ms 114964 KB Output is correct
22 Correct 729 ms 112336 KB Output is correct
23 Correct 793 ms 112400 KB Output is correct
24 Correct 748 ms 112420 KB Output is correct
25 Correct 746 ms 112352 KB Output is correct
26 Correct 754 ms 114924 KB Output is correct
27 Correct 779 ms 114916 KB Output is correct
28 Correct 733 ms 112420 KB Output is correct
29 Correct 730 ms 112460 KB Output is correct
30 Correct 725 ms 112468 KB Output is correct