oj.uz

Submission #770980

# Submission time Handle Problem Language Result Execution time Memory
770980 2023-07-02T09:06:00 Z loctildore Wall (IOI14_wall) C++14
100 / 100
 620 ms 232384 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)

int arr[2000069];

void merge(pair<int, int> &x, pair<int, int> y) {
    if (y.s < x.f) x = {y.s, y.s};
    else if (y.f > x.s) x = {y.f, y.f};
    else x = {max(x.f, y.f), min(x.s, y.s)};
}

struct node {
    int l, r;
    node *lft, *rht;
    pair<int, int> val;

    node(int tl, int tr): l(tl), r(tr), val({0, INT_MAX}) {
        if (l + 1 == r) {
            lft = rht = NULL;
            return;
        }
        lft = new node(l, (l + r) / 2);
        rht = new node((l + r) / 2, r);
    }

    void clean() {
        if (l + 1 == r) return;
        merge(lft->val, val);
        merge(rht->val, val);
        val = {0, INT_MAX};
    }

    void upd(int tl, int tr, pair<int,int> nw) {
        if (tr <= l || r <= tl) return;
        if (tl <= l && r <= tr) {
            merge(val, nw);
            return;
        }
        clean();
        lft->upd(tl, tr, nw);
        rht->upd(tl, tr, nw);
    }

    void outp() {
        if (l + 1 == r) {
            arr[l] = val.f;
            return;
        }
        clean();
        lft->outp();
        rht->outp();
    }
} *root;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    root = new node(0, n);
    for (int i = 0; i < k; i++) {
        pair<int,int> tmp = {0, INT_MAX};
        if (op[i] == 1) tmp.f = height[i];
        else tmp.s = height[i];
        root->upd(left[i], right[i] + 1, tmp);
    }
    root->outp();
    for (int i = 0; i < n; i++) {
        finalHeight[i] = arr[i];
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 1476 KB Output is correct
5 Correct 4 ms 1492 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 101 ms 13864 KB Output is correct
3 Correct 116 ms 9268 KB Output is correct
4 Correct 338 ms 28064 KB Output is correct
5 Correct 198 ms 29096 KB Output is correct
6 Correct 189 ms 27544 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 5 ms 1492 KB Output is correct
5 Correct 4 ms 1536 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 100 ms 13880 KB Output is correct
9 Correct 120 ms 9292 KB Output is correct
10 Correct 339 ms 28028 KB Output is correct
11 Correct 201 ms 29092 KB Output is correct
12 Correct 203 ms 27540 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 101 ms 13940 KB Output is correct
15 Correct 24 ms 3112 KB Output is correct
16 Correct 430 ms 28296 KB Output is correct
17 Correct 199 ms 27684 KB Output is correct
18 Correct 199 ms 27684 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 1448 KB Output is correct
5 Correct 5 ms 1492 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 100 ms 13860 KB Output is correct
9 Correct 114 ms 9240 KB Output is correct
10 Correct 337 ms 28068 KB Output is correct
11 Correct 200 ms 29100 KB Output is correct
12 Correct 191 ms 27540 KB Output is correct
13 Correct 0 ms 308 KB Output is correct
14 Correct 102 ms 13880 KB Output is correct
15 Correct 24 ms 3068 KB Output is correct
16 Correct 415 ms 28300 KB Output is correct
17 Correct 201 ms 27716 KB Output is correct
18 Correct 205 ms 27724 KB Output is correct
19 Correct 620 ms 232264 KB Output is correct
20 Correct 593 ms 229836 KB Output is correct
21 Correct 604 ms 232372 KB Output is correct
22 Correct 609 ms 229876 KB Output is correct
23 Correct 592 ms 229836 KB Output is correct
24 Correct 592 ms 229764 KB Output is correct
25 Correct 591 ms 229860 KB Output is correct
26 Correct 607 ms 232332 KB Output is correct
27 Correct 596 ms 232384 KB Output is correct
28 Correct 588 ms 229776 KB Output is correct
29 Correct 598 ms 229816 KB Output is correct
30 Correct 601 ms 229860 KB Output is correct