oj.uz

Submission #986885

# Submission time Handle Problem Language Result Execution time Memory
986885 2024-05-21T13:52:34 Z MuntherCarrot Wall (IOI14_wall) C++14
61 / 100
 449 ms 29268 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] = max(add[i << 1], add[i]);
        add[i << 1] = min(add[i << 1], del[i]);
        del[i << 1] = max(del[i << 1], add[i]);
        del[i << 1] = min(del[i << 1], del[i]);
        add[i << 1 | 1] = max(add[i << 1 | 1], add[i]);
        add[i << 1 | 1] = min(add[i << 1 | 1], del[i]);
        del[i << 1 | 1] = max(del[i << 1 | 1], add[i]);
        del[i << 1 | 1] = min(del[i << 1 | 1], del[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 3420 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 3628 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 6 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 223 ms 11268 KB Output is correct
3 Correct 158 ms 6652 KB Output is correct
4 Correct 437 ms 11912 KB Output is correct
5 Correct 252 ms 12372 KB Output is correct
6 Correct 250 ms 12236 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 4 ms 3416 KB Output is correct
3 Correct 3 ms 3420 KB Output is correct
4 Correct 6 ms 3608 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 6 ms 3928 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 217 ms 11272 KB Output is correct
9 Correct 161 ms 6860 KB Output is correct
10 Correct 441 ms 11924 KB Output is correct
11 Correct 265 ms 12316 KB Output is correct
12 Correct 249 ms 12368 KB Output is correct
13 Correct 2 ms 3416 KB Output is correct
14 Correct 223 ms 11480 KB Output is correct
15 Correct 27 ms 3920 KB Output is correct
16 Correct 448 ms 12168 KB Output is correct
17 Correct 254 ms 12004 KB Output is correct
18 Correct 253 ms 12000 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 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 3484 KB Output is correct
6 Correct 6 ms 3676 KB Output is correct
7 Correct 2 ms 3416 KB Output is correct
8 Correct 216 ms 11240 KB Output is correct
9 Correct 158 ms 6736 KB Output is correct
10 Correct 438 ms 11908 KB Output is correct
11 Correct 253 ms 12372 KB Output is correct
12 Correct 249 ms 12208 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 228 ms 11240 KB Output is correct
15 Correct 27 ms 4036 KB Output is correct
16 Correct 449 ms 12400 KB Output is correct
17 Correct 253 ms 12112 KB Output is correct
18 Correct 256 ms 12112 KB Output is correct
19 Runtime error 151 ms 29268 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -