oj.uz

Submission #697944

# Submission time Handle Problem Language Result Execution time Memory
697944 2023-02-11T14:27:07 Z BhavayGoyal Wall (IOI14_wall) C++14
100 / 100
 897 ms 65588 KB 
#include <bits/stdc++.h>
#include <wall.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};


// -------------------------------------------------- Main Code --------------------------------------------------

struct Node {
    int val, mn, mx; // final value, last was delete oper, last was add oper
};

struct segTree {
    int n;
    vector<Node> tree;

    segTree(int N) {n = 1; while (n < N) n *= 2; tree = vector<Node>(2*n+2, {0, inf, -1});}

    void propogate(int node, int left, int right) {
        if (tree[node].mn == inf && tree[node].mx == -1) return;

        if (tree[node].mn != inf) {
            tree[node].val = min(tree[node].val, tree[node].mn);
            if (left != right) {
                tree[node*2].mx = min(tree[node].mn, tree[node*2].mx);
                tree[node*2].mn = min(tree[node].mn, tree[node*2].mn);
                tree[node*2+1].mx = min(tree[node].mn, tree[node*2+1].mx);
                tree[node*2+1].mn = min(tree[node].mn, tree[node*2+1].mn);
            }
            tree[node].mn = inf;
        }
        if (tree[node].mx != -1) {
            tree[node].val = max(tree[node].val, tree[node].mx);
            if (left != right) {
                tree[node*2].mn = max(tree[node].mx, tree[node*2].mn);
                tree[node*2].mx = max(tree[node].mx, tree[node*2].mx);
                tree[node*2+1].mn = max(tree[node].mx, tree[node*2+1].mn);
                tree[node*2+1].mx = max(tree[node].mx, tree[node*2+1].mx);
            }
            tree[node].mx = -1;
        }
    }

    void update(int node, int left, int right, int l, int r, int val, int type) {
        propogate(node, left, right);
        if (left > r || right < l) return;
        else if (left >= l && right <= r) {
            if (type == 1) {
                // add operation
                tree[node].mn = inf;
                tree[node].mx = val;
            }
            else {
                // delete operation
                tree[node].mn = val;
                tree[node].mx = -1;
            }
            propogate(node, left, right);
            return;
        }
        update(node*2, left, (left+right)/2, l, r, val, type);
        update(node*2+1, (left+right)/2+1, right, l, r, val, type);
    }
    void update(int l, int r, int val, int type) {update(1, 1, n, l, r, val, type);}

    int query(int node, int left, int right, int idx) {
        propogate(node, left, right);
        if (left == right) {
            return tree[node].val;
        }
        int mid = (left+right)/2;
        if (idx <= mid) return query(node*2, left, (left+right)/2, idx);
        else return query(node*2+1, (left+right)/2+1, right, idx);
    }
    int query(int idx) {return query(1, 1, n, idx);}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    segTree tree(n);
    for (int i = 0; i < k; i++) tree.update(left[i]+1, right[i]+1, height[i], op[i]);
    for (int i = 0; i < n; i++) finalHeight[i] = tree.query(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 376 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 884 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 5 ms 820 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 118 ms 8096 KB Output is correct
3 Correct 181 ms 4396 KB Output is correct
4 Correct 497 ms 11852 KB Output is correct
5 Correct 249 ms 11852 KB Output is correct
6 Correct 261 ms 11776 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 125 ms 8352 KB Output is correct
9 Correct 183 ms 4680 KB Output is correct
10 Correct 494 ms 11912 KB Output is correct
11 Correct 250 ms 11980 KB Output is correct
12 Correct 243 ms 11980 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 121 ms 8404 KB Output is correct
15 Correct 36 ms 1692 KB Output is correct
16 Correct 610 ms 11976 KB Output is correct
17 Correct 257 ms 12068 KB Output is correct
18 Correct 249 ms 11984 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 824 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 6 ms 884 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 122 ms 8336 KB Output is correct
9 Correct 183 ms 4528 KB Output is correct
10 Correct 501 ms 11924 KB Output is correct
11 Correct 253 ms 11852 KB Output is correct
12 Correct 249 ms 12000 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 121 ms 8492 KB Output is correct
15 Correct 37 ms 1724 KB Output is correct
16 Correct 615 ms 11944 KB Output is correct
17 Correct 250 ms 12088 KB Output is correct
18 Correct 254 ms 11940 KB Output is correct
19 Correct 848 ms 65416 KB Output is correct
20 Correct 847 ms 65512 KB Output is correct
21 Correct 851 ms 65484 KB Output is correct
22 Correct 843 ms 65552 KB Output is correct
23 Correct 836 ms 65552 KB Output is correct
24 Correct 836 ms 65544 KB Output is correct
25 Correct 841 ms 65580 KB Output is correct
26 Correct 840 ms 65584 KB Output is correct
27 Correct 845 ms 65356 KB Output is correct
28 Correct 858 ms 65452 KB Output is correct
29 Correct 897 ms 65576 KB Output is correct
30 Correct 890 ms 65588 KB Output is correct