Submission #725712

#	Time	Username	Problem	Language	Result	Execution time	Memory
725712		Abrar_Al_Samit	Wall (IOI14_wall)	C++17	61 / 100	391 ms	58352 KiB

wall

#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]+1, right[i]+1, height[i], 1);
        } else {
            minimize(1, n, left[i]+1, right[i]+1, height[i], 1);
        }
    }
    for(int i=0; i<n; ++i) {
        finalHeight[i] = query(1, n, i+1, 1);
    }
    return;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39