oj.uz

Submission #986892

# Submission time Handle Problem Language Result Execution time Memory
986892 2024-05-21T13:57:22 Z MuntherCarrot Wall (IOI14_wall) C++14
100 / 100
 822 ms 233508 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1 << 23;
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 128 ms 197460 KB Output is correct
2 Correct 133 ms 197424 KB Output is correct
3 Correct 128 ms 197204 KB Output is correct
4 Correct 132 ms 197460 KB Output is correct
5 Correct 131 ms 197420 KB Output is correct
6 Correct 135 ms 197968 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 197188 KB Output is correct
2 Correct 416 ms 205156 KB Output is correct
3 Correct 310 ms 200788 KB Output is correct
4 Correct 612 ms 205864 KB Output is correct
5 Correct 427 ms 206108 KB Output is correct
6 Correct 464 ms 206332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 197236 KB Output is correct
2 Correct 131 ms 197340 KB Output is correct
3 Correct 130 ms 197456 KB Output is correct
4 Correct 131 ms 197456 KB Output is correct
5 Correct 132 ms 197416 KB Output is correct
6 Correct 134 ms 197524 KB Output is correct
7 Correct 129 ms 197200 KB Output is correct
8 Correct 415 ms 205252 KB Output is correct
9 Correct 310 ms 200788 KB Output is correct
10 Correct 608 ms 205652 KB Output is correct
11 Correct 439 ms 206408 KB Output is correct
12 Correct 423 ms 206284 KB Output is correct
13 Correct 149 ms 197200 KB Output is correct
14 Correct 407 ms 205016 KB Output is correct
15 Correct 168 ms 198000 KB Output is correct
16 Correct 638 ms 206052 KB Output is correct
17 Correct 422 ms 205892 KB Output is correct
18 Correct 470 ms 206064 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 197200 KB Output is correct
2 Correct 131 ms 197468 KB Output is correct
3 Correct 128 ms 197204 KB Output is correct
4 Correct 135 ms 197444 KB Output is correct
5 Correct 131 ms 197352 KB Output is correct
6 Correct 133 ms 197460 KB Output is correct
7 Correct 142 ms 197204 KB Output is correct
8 Correct 420 ms 205112 KB Output is correct
9 Correct 306 ms 200556 KB Output is correct
10 Correct 628 ms 205640 KB Output is correct
11 Correct 426 ms 206152 KB Output is correct
12 Correct 420 ms 206144 KB Output is correct
13 Correct 126 ms 197312 KB Output is correct
14 Correct 414 ms 205128 KB Output is correct
15 Correct 155 ms 197972 KB Output is correct
16 Correct 631 ms 206008 KB Output is correct
17 Correct 435 ms 206192 KB Output is correct
18 Correct 480 ms 205976 KB Output is correct
19 Correct 822 ms 223320 KB Output is correct
20 Correct 765 ms 230676 KB Output is correct
21 Correct 796 ms 233396 KB Output is correct
22 Correct 792 ms 230880 KB Output is correct
23 Correct 787 ms 230636 KB Output is correct
24 Correct 771 ms 230744 KB Output is correct
25 Correct 762 ms 230740 KB Output is correct
26 Correct 795 ms 233508 KB Output is correct
27 Correct 783 ms 233352 KB Output is correct
28 Correct 763 ms 230628 KB Output is correct
29 Correct 808 ms 230784 KB Output is correct
30 Correct 763 ms 230736 KB Output is correct