oj.uz

Submission #986886

# Submission time Handle Problem Language Result Execution time Memory
986886 2024-05-21T13:53:49 Z vjudge1 Wall (IOI14_wall) C++17
61 / 100
 463 ms 25596 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1 << 17;
int add[N << 2], del[N << 2];

void push(int i, int l, int r){
    if(l != r){
        add[i << 1] = min(add[i << 1], del[i]);
        add[i << 1] = max(add[i << 1], add[i]);
        del[i << 1] = min(del[i << 1], del[i]);
        del[i << 1] = max(del[i << 1], add[i]);
        add[i << 1 | 1] = min(add[i << 1 | 1], del[i]);
        add[i << 1 | 1] = max(add[i << 1 | 1], add[i]);
        del[i << 1 | 1] = min(del[i << 1 | 1], del[i]);
        del[i << 1 | 1] = max(del[i << 1 | 1], add[i]);
        add[i] = 0, del[i] = INF;
    }
}

void updAdd(int l, int r, int i, int from, int to, int val){
    push(i, from, to);
    if (from > r || to < l)
        return;
    if (from >= l && to <= r)
    {
        add[i] = max(add[i], val);
        del[i] = max(del[i], val);
        push(i, from, to);
        return;
    }
    int mid = (from + to) >> 1;
    updAdd(l, r, i << 1, from, mid, val);
    updAdd(l, r, i << 1 | 1, mid + 1, to, val);
}

void updDel(int l, int r, int i, int from, int to, int val){
    push(i, from, to);
    if(from > r || to < l) return;
    if(from >= l && to <= r){
        add[i] = min(add[i], val);
        del[i] = min(del[i], val);
        push(i, from, to);
        return;
    }
    int mid = (from + to) >> 1;
    updDel(l, r, i << 1, from, mid, val);
    updDel(l, r, i << 1 | 1, mid + 1, to , val);
}

void pushall(int i, int l, int r){
    if(l == r) return;
    push(i, l, r);
    int mid = (l + r) >> 1;
    pushall(i << 1, l, mid);
    pushall(i << 1 | 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
    memset(del, INF, sizeof del);
    for(int i = 0; i < k; i++){
        if(op[i] == 1){
            updAdd(l[i], r[i], 1, 0, N - 1, h[i]);
        }
        else{
            updDel(l[i], r[i], 1, 0, N - 1, h[i]);
        }
    }
    pushall(1, 0, N - 1);
    for(int i = 0; i < n; i++){
        ans[i] = min(add[i + N], del[i + N]);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 3 ms 3420 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 6 ms 3632 KB Output is correct
6 Correct 8 ms 3672 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 213 ms 11348 KB Output is correct
3 Correct 175 ms 6856 KB Output is correct
4 Correct 460 ms 11956 KB Output is correct
5 Correct 253 ms 12372 KB Output is correct
6 Correct 252 ms 12244 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 6 ms 3676 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 220 ms 11312 KB Output is correct
9 Correct 157 ms 6732 KB Output is correct
10 Correct 443 ms 12112 KB Output is correct
11 Correct 296 ms 12368 KB Output is correct
12 Correct 249 ms 12328 KB Output is correct
13 Correct 2 ms 3416 KB Output is correct
14 Correct 229 ms 11256 KB Output is correct
15 Correct 26 ms 3928 KB Output is correct
16 Correct 443 ms 12164 KB Output is correct
17 Correct 251 ms 12344 KB Output is correct
18 Correct 248 ms 12112 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 5 ms 3620 KB Output is correct
3 Correct 3 ms 3420 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 6 ms 3676 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 231 ms 11348 KB Output is correct
9 Correct 156 ms 6856 KB Output is correct
10 Correct 463 ms 11920 KB Output is correct
11 Correct 251 ms 12372 KB Output is correct
12 Correct 276 ms 12424 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 218 ms 11268 KB Output is correct
15 Correct 26 ms 3928 KB Output is correct
16 Correct 445 ms 12364 KB Output is correct
17 Correct 250 ms 12164 KB Output is correct
18 Correct 337 ms 12004 KB Output is correct
19 Runtime error 165 ms 25596 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -