oj.uz

Submission #986889

# Submission time Handle Problem Language Result Execution time Memory
986889 2024-05-21T13:55:57 Z vjudge1 Wall (IOI14_wall) C++17
61 / 100
 479 ms 36060 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1 << 18;
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 3 ms 6492 KB Output is correct
2 Correct 6 ms 6492 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 8 ms 6744 KB Output is correct
5 Correct 8 ms 6744 KB Output is correct
6 Correct 8 ms 6724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 227 ms 14232 KB Output is correct
3 Correct 166 ms 9928 KB Output is correct
4 Correct 455 ms 15028 KB Output is correct
5 Correct 262 ms 15444 KB Output is correct
6 Correct 277 ms 15440 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 6 ms 6492 KB Output is correct
3 Correct 5 ms 6504 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 7 ms 6748 KB Output is correct
6 Correct 8 ms 6772 KB Output is correct
7 Correct 4 ms 6492 KB Output is correct
8 Correct 224 ms 14352 KB Output is correct
9 Correct 193 ms 9916 KB Output is correct
10 Correct 439 ms 14928 KB Output is correct
11 Correct 266 ms 15340 KB Output is correct
12 Correct 285 ms 15420 KB Output is correct
13 Correct 4 ms 6492 KB Output is correct
14 Correct 250 ms 14352 KB Output is correct
15 Correct 36 ms 7260 KB Output is correct
16 Correct 479 ms 15044 KB Output is correct
17 Correct 279 ms 15044 KB Output is correct
18 Correct 301 ms 15032 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 9 ms 6488 KB Output is correct
3 Correct 5 ms 6744 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 8 ms 6748 KB Output is correct
6 Correct 8 ms 6748 KB Output is correct
7 Correct 4 ms 6492 KB Output is correct
8 Correct 299 ms 14424 KB Output is correct
9 Correct 162 ms 9812 KB Output is correct
10 Correct 443 ms 15020 KB Output is correct
11 Correct 273 ms 15420 KB Output is correct
12 Correct 258 ms 15444 KB Output is correct
13 Correct 4 ms 6492 KB Output is correct
14 Correct 278 ms 14360 KB Output is correct
15 Correct 28 ms 7004 KB Output is correct
16 Correct 474 ms 15048 KB Output is correct
17 Correct 269 ms 15132 KB Output is correct
18 Correct 256 ms 15180 KB Output is correct
19 Runtime error 196 ms 36060 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -