oj.uz

Submission #725710

# Submission time Handle Problem Language Result Execution time Memory
725710 2023-04-17T23:39:48 Z Abrar_Al_Samit Wall (IOI14_wall) C++17
0 / 100
 10 ms 15956 KB 
#include <bits/stdc++.h>
using namespace std;
#include "wall.h"

const int INF = 1e9;
const int nax = 5e5 + 3;

pair<int, int>st[nax * 4];


void propagate(int v) {
    for(int c : {v*2, v*2+1}) {
        st[c].first = max(st[v].first, st[c].first);
        st[c].second = max(st[c].first, st[c].second);

        st[c].second = min(st[c].second, st[v].second);
        st[c].first = min(st[c].first, st[c].second);
    }
    st[v] = {-INF, INF};
}
void maximize(int l, int r, int L, int R, int val, int v) {
    if(l>R || r<L) return;
    if(l>=L && r<=R) {
        st[v].first = max(st[v].first, val);
        st[v].second = max(st[v].first, st[v].second);
        return;
    }
    propagate(v);
    int mid = (l+r)/2;
    maximize(l, mid, L, R, val, v*2);
    maximize(mid+1, r, L, R, val, v*2+1);
}
void minimize(int l, int r, int L, int R, int val, int v) {
    if(l>R || r<L) return;
    if(l>=L && r<=R) {
        st[v].second = min(st[v].second, val);
        st[v].first = min(st[v].first, st[v].second);
        return;
    }
    propagate(v);
    int mid = (l+r)/2;
    minimize(l, mid, L, R, val, v*2);
    minimize(mid+1, r, L, R, val, v*2+1);   
}
int query(int l, int r, int p, int v) {
    if(l==r) {
        return min(max(0, st[v].first), st[v].second);
    }
    propagate(v);
    int mid = (l+r)/2;
    if(p<=mid) return query(l, mid, p, v*2);
    else return query(mid+1, r, p, v*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=1; i<nax * 4; ++i) {
        st[i] = {-INF, INF};
    }
    for(int i=0; i<k; ++i) {
        if(op[i]==1) {
            maximize(1, n, left[i], right[i], height[i], 1);
        } else {
            minimize(1, n, left[i], right[i], height[i], 1);
        }
    }
    for(int i=0; i<n; ++i) {
        finalHeight[i] = query(1, n, i, 1);
    }
    return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 15924 KB Output isn't correct
2 Halted 0 ms 0 KB -