oj.uz

Submission #986878

# Submission time Handle Problem Language Result Execution time Memory
986878 2024-05-21T13:41:26 Z MuntherCarrot Wall (IOI14_wall) C++14
61 / 100
 449 ms 41044 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1 << 17;
int t[N << 2];
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]);
    }
}

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

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++){
        upd(l[i], r[i], 1, 0, N - 1, h[i], op[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 3420 KB Output is correct
2 Correct 5 ms 3652 KB Output is correct
3 Correct 3 ms 3572 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 8 ms 3672 KB Output is correct
6 Correct 6 ms 3676 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 251 ms 16276 KB Output is correct
3 Correct 178 ms 9376 KB Output is correct
4 Correct 445 ms 19824 KB Output is correct
5 Correct 278 ms 20672 KB Output is correct
6 Correct 266 ms 19556 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 3524 KB Output is correct
3 Correct 3 ms 3420 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 8 ms 3768 KB Output is correct
6 Correct 6 ms 3696 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 234 ms 16140 KB Output is correct
9 Correct 159 ms 10064 KB Output is correct
10 Correct 448 ms 19852 KB Output is correct
11 Correct 271 ms 20560 KB Output is correct
12 Correct 273 ms 19432 KB Output is correct
13 Correct 2 ms 3416 KB Output is correct
14 Correct 236 ms 16212 KB Output is correct
15 Correct 32 ms 4688 KB Output is correct
16 Correct 441 ms 20000 KB Output is correct
17 Correct 276 ms 19432 KB Output is correct
18 Correct 270 ms 19540 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3416 KB Output is correct
2 Correct 5 ms 3416 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 251 ms 16096 KB Output is correct
9 Correct 162 ms 10204 KB Output is correct
10 Correct 449 ms 19852 KB Output is correct
11 Correct 272 ms 20400 KB Output is correct
12 Correct 271 ms 19592 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 234 ms 16168 KB Output is correct
15 Correct 27 ms 4492 KB Output is correct
16 Correct 443 ms 20048 KB Output is correct
17 Correct 277 ms 19596 KB Output is correct
18 Correct 273 ms 19472 KB Output is correct
19 Runtime error 209 ms 41044 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -