oj.uz

Submission #931203

# Submission time Handle Problem Language Result Execution time Memory
931203 2024-02-21T11:25:25 Z VMaksimoski008 Wall (IOI14_wall) C++14
100 / 100
 801 ms 120656 KB 
#include <bits/stdc++.h>
#include "wall.h"
 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

struct SegTree {
    int n;
    vector<int> tree;
    vector<pii> lazy;

    SegTree(int _n) {
        n = _n;
        tree.resize(4*n+5, 0);
        lazy.resize(4*n+5, {1e9, -1});
    }

    void push(int u, int tl, int tr) {
        if(tl == tr) return ;

        if(lazy[u].first != 1e9) {
            tree[2*u] = min(tree[2*u], lazy[u].first);
            lazy[2*u].first = min(lazy[2*u].first, lazy[u].first);
            lazy[2*u].second = min(lazy[2*u].second, lazy[u].first);

            tree[2*u+1] = min(tree[2*u+1], lazy[u].first);
            lazy[2*u+1].first = min(lazy[2*u+1].first, lazy[u].first);
            lazy[2*u+1].second = min(lazy[2*u+1].second, lazy[u].first);
        }

        if(lazy[u].second != -1) {
            tree[2*u] = max(tree[2*u], lazy[u].second);
            lazy[2*u].first = max(lazy[2*u].first, lazy[u].second);
            lazy[2*u].second = max(lazy[2*u].second, lazy[u].second);

            tree[2*u+1] = max(tree[2*u+1], lazy[u].second);
            lazy[2*u+1].first = max(lazy[2*u+1].first, lazy[u].second);
            lazy[2*u+1].second = max(lazy[2*u+1].second, lazy[u].second);
        }

        lazy[u] = {1e9, -1};
    }

    void update(int u, int tl, int tr, int l, int r, int t, int v) {
        push(u, tl, tr);
        if(tl > tr || l > tr || tl > r) return ;

        if(l <= tl && tr <= r) {
            if(t == 1) {
                tree[u] = max(tree[u], v);
                lazy[u].first = max(lazy[u].first, v);
                lazy[u].second = max(lazy[u].second, v);
            } else {
                tree[u] = min(tree[u], v);
                lazy[u].first = min(lazy[u].first, v);
                lazy[u].second = min(lazy[u].second, v);
            }

            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, t, v);
        update(2*u+1, tm+1, tr, l, r, t, v);
    }

    int query(int u, int tl, int tr, int p) {
        if(tl == tr) return tree[u];
        push(u, tl, tr);
        int tm = (tl + tr) / 2;
        if(p <= tm) return query(2*u, tl, tm, p);
        return query(2*u+1, tm+1, tr, p);
    }   

    void update(int l, int r, int t, int v) { update(1, 0, n-1, l, r, t, v); }
    int query(int p) { return query(1, 0, n-1, p); }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for(int i=0; i<n; i++) finalHeight[i] = 0;

    SegTree tree(n);
 
    for(int i=0; i<k; i++)
        tree.update(left[i], right[i], op[i], height[i]);
    for(int i=0; i<n; i++)
        finalHeight[i] = tree.query(i);
}
 
// int32_t main() {
//     int n, k;
//     cin >> n >> k;
 
//     int op[n], left[n], right[n], height[n], finalHeight[n];
 
//     for(int i=0; i<k; i++)
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
 
//     buildWall(n, k, op, left, right, height, finalHeight);
//     return 0;
// }

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 452 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 6 ms 1368 KB Output is correct
5 Correct 5 ms 1116 KB Output is correct
6 Correct 5 ms 888 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 101 ms 13840 KB Output is correct
3 Correct 181 ms 7380 KB Output is correct
4 Correct 492 ms 22956 KB Output is correct
5 Correct 232 ms 23708 KB Output is correct
6 Correct 223 ms 21840 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 2 ms 344 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 6 ms 1048 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 101 ms 13908 KB Output is correct
9 Correct 161 ms 8388 KB Output is correct
10 Correct 503 ms 22960 KB Output is correct
11 Correct 223 ms 23500 KB Output is correct
12 Correct 220 ms 21844 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 104 ms 13896 KB Output is correct
15 Correct 39 ms 2140 KB Output is correct
16 Correct 598 ms 22984 KB Output is correct
17 Correct 223 ms 22356 KB Output is correct
18 Correct 227 ms 22328 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 560 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 7 ms 960 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 101 ms 14032 KB Output is correct
9 Correct 164 ms 8244 KB Output is correct
10 Correct 480 ms 22864 KB Output is correct
11 Correct 233 ms 23380 KB Output is correct
12 Correct 220 ms 21948 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 104 ms 13980 KB Output is correct
15 Correct 33 ms 2140 KB Output is correct
16 Correct 608 ms 22860 KB Output is correct
17 Correct 233 ms 22608 KB Output is correct
18 Correct 226 ms 22400 KB Output is correct
19 Correct 766 ms 120460 KB Output is correct
20 Correct 753 ms 120456 KB Output is correct
21 Correct 749 ms 120312 KB Output is correct
22 Correct 741 ms 120400 KB Output is correct
23 Correct 801 ms 120400 KB Output is correct
24 Correct 753 ms 120460 KB Output is correct
25 Correct 746 ms 120400 KB Output is correct
26 Correct 747 ms 120400 KB Output is correct
27 Correct 756 ms 120396 KB Output is correct
28 Correct 737 ms 120396 KB Output is correct
29 Correct 748 ms 120656 KB Output is correct
30 Correct 762 ms 120460 KB Output is correct