oj.uz

Submission #1043040

# Submission time Handle Problem Language Result Execution time Memory
1043040 2024-08-03T18:47:27 Z vanea Wall (IOI14_wall) C++14
100 / 100
 985 ms 69716 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
using ld = long double;

const int mxN = 1e7;
const int INF = 1e9+10;

array<int, 2> st[mxN];

void build(int node, int l, int r) {
    if(l == r) {
        st[node] = {0, INF};
        return ;
    }
    int mid = (l+r)/2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    st[node] = {0, INF};
}

void propagate(int node, int l, int r) {
    if(l == r) return ;
    int left = node*2, right = node*2+1;
    st[left][1] = min(st[left][1], st[node][1]);
    st[left][1] = max(st[left][1], st[node][0]);
    st[left][0] = max(st[left][0], st[node][0]);
    st[left][0] = min(st[left][0], st[node][1]);
    st[right][1] = min(st[right][1], st[node][1]);
    st[right][1] = max(st[right][1], st[node][0]);
    st[right][0] = max(st[right][0], st[node][0]);
    st[right][0] = min(st[right][0], st[node][1]);
    st[node][0] = 0;
    st[node][1] = INF;
}

void upd(int node, int l, int r, int l1, int r1, int h, int op) {
    propagate(node, l, r);
    if(l1 <= l && r1 >= r) {
        if(op == 1) {
            st[node][0] = max(st[node][0], h);
            st[node][1] = max(st[node][1], h);
        }
        else {
            st[node][1] = min(st[node][1], h);
            st[node][0] = min(st[node][0], h);
        }
        propagate(node, l, r);
        return ;
    }
    if(l1 > r || r1 < l) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, l1, r1, h, op);
    upd(node*2+1, mid+1, r, l1, r1, h, op);
}

int query(int node, int l, int r, int k) {
    propagate(node, l, r);
    if(l == r && l == k) {
        return min(st[node][0], st[node][1]);
    }
    if(l > k || r < k) return 0;
    int mid = (l+r)/2;
    return query(node*2, l, mid, k) + query(node*2+1, mid+1, r, k);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1, 0, n-1);
    for(int i = 0; i < k; i++) {
        upd(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    for(int i = 0; i < n; i++) {
        finalHeight[i] = query(1, 0, n-1, i);
        //cout << finalHeight[i] << ' ';
    }
}

/*
int main()
{
    int arr1[10] = {1, 2, 2, 1, 1, 2}, arr2[10] = {1, 4, 3, 0, 2, 6};
    int arr3[10] = {8, 9, 6, 5, 2, 7}, arr4[10] = {4, 1, 5, 3, 5, 0};
    int arr5[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    buildWall(10, 6, arr1, arr2, arr3, arr4, arr5);
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 5 ms 2908 KB Output is correct
6 Correct 5 ms 2692 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 71 ms 14072 KB Output is correct
3 Correct 136 ms 9760 KB Output is correct
4 Correct 390 ms 20664 KB Output is correct
5 Correct 226 ms 21584 KB Output is correct
6 Correct 223 ms 20048 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 9 ms 2756 KB Output is correct
5 Correct 5 ms 2908 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 75 ms 13832 KB Output is correct
9 Correct 123 ms 9728 KB Output is correct
10 Correct 371 ms 20560 KB Output is correct
11 Correct 235 ms 21644 KB Output is correct
12 Correct 222 ms 20048 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 73 ms 13976 KB Output is correct
15 Correct 24 ms 3728 KB Output is correct
16 Correct 364 ms 20944 KB Output is correct
17 Correct 230 ms 20240 KB Output is correct
18 Correct 244 ms 20360 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 1 ms 348 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 5 ms 2908 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 71 ms 13992 KB Output is correct
9 Correct 124 ms 9812 KB Output is correct
10 Correct 364 ms 20564 KB Output is correct
11 Correct 224 ms 21584 KB Output is correct
12 Correct 220 ms 20160 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 75 ms 13908 KB Output is correct
15 Correct 25 ms 3672 KB Output is correct
16 Correct 358 ms 20812 KB Output is correct
17 Correct 226 ms 20172 KB Output is correct
18 Correct 217 ms 20208 KB Output is correct
19 Correct 945 ms 69716 KB Output is correct
20 Correct 985 ms 67328 KB Output is correct
21 Correct 929 ms 69632 KB Output is correct
22 Correct 945 ms 67324 KB Output is correct
23 Correct 922 ms 67300 KB Output is correct
24 Correct 920 ms 67152 KB Output is correct
25 Correct 972 ms 67260 KB Output is correct
26 Correct 927 ms 69712 KB Output is correct
27 Correct 960 ms 69716 KB Output is correct
28 Correct 922 ms 67156 KB Output is correct
29 Correct 911 ms 67300 KB Output is correct
30 Correct 926 ms 67156 KB Output is correct