oj.uz

Submission #986897

# Submission time Handle Problem Language Result Execution time Memory
986897 2024-05-21T14:03:48 Z MuntherCarrot Wall (IOI14_wall) C++14
0 / 100
 197 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1 << 23;
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]);
        t[i << 1] = min(t[i << 1], del[i]);
        t[i << 1] = max(t[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]);
        t[i << 1 | 1] = min(t[i << 1 | 1], del[i]);
        t[i << 1 | 1] = max(t[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);
        t[i] = max(t[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);
    t[i] = min(t[i << 1], t[i << 1 | 1]);
}

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);
        t[i] = min(t[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);
    t[i] = min(t[i << 1], t[i << 1 | 1]);
}

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] = t[i + N];
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -