oj.uz

Submission #986884

# Submission time Handle Problem Language Result Execution time Memory
986884 2024-05-21T13:50:44 Z MuntherCarrot Wall (IOI14_wall) C++14
61 / 100
 467 ms 25836 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] = add[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 3676 KB Output is correct
6 Correct 7 ms 3676 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3512 KB Output is correct
2 Correct 223 ms 14612 KB Output is correct
3 Correct 159 ms 6856 KB Output is correct
4 Correct 457 ms 11936 KB Output is correct
5 Correct 252 ms 12420 KB Output is correct
6 Correct 254 ms 12428 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 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 220 ms 11268 KB Output is correct
9 Correct 157 ms 6736 KB Output is correct
10 Correct 429 ms 11912 KB Output is correct
11 Correct 255 ms 12368 KB Output is correct
12 Correct 249 ms 12240 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 225 ms 11272 KB Output is correct
15 Correct 26 ms 3932 KB Output is correct
16 Correct 467 ms 12116 KB Output is correct
17 Correct 256 ms 12356 KB Output is correct
18 Correct 251 ms 12112 KB Output is correct

Subtask #4
0 / 39.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 4 ms 3420 KB Output is correct
4 Correct 6 ms 3672 KB Output is correct
5 Correct 6 ms 3676 KB Output is correct
6 Correct 6 ms 3672 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 216 ms 11112 KB Output is correct
9 Correct 158 ms 6736 KB Output is correct
10 Correct 433 ms 11748 KB Output is correct
11 Correct 253 ms 12460 KB Output is correct
12 Correct 247 ms 12368 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 218 ms 11156 KB Output is correct
15 Correct 27 ms 3924 KB Output is correct
16 Correct 433 ms 12108 KB Output is correct
17 Correct 258 ms 12368 KB Output is correct
18 Correct 249 ms 12116 KB Output is correct
19 Runtime error 150 ms 25836 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -