Submission #1062929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062929		anango	Wall (IOI14_wall)	C++17	100 / 100	1667 ms	91988 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

int INF = 1<<30;

const int sz = 4194304;

int mins[sz]; //apply mins before maxes
int maxes[sz];
int lazymins[sz];
int lazymaxes[sz];

void mergemin(int v, int c) {
    int a = mins[v];
    int b = maxes[v];
    a = min(a,c);
    b = min(b,c);
    mins[v] = a;
    maxes[v] = b;
}

void mergemax(int v, int c) {
    int a = mins[v];
    int b = maxes[v];
    b = max(b,c);
    mins[v] = a;
    maxes[v] = b;
}

void lazymergemin(int v, int c) {
    int a = lazymins[v];
    int b = lazymaxes[v];
    a = min(a,c);
    b = min(b,c);
    lazymins[v] = a;
    lazymaxes[v] = b;
}

void lazymergemax(int v, int c) {
    int a = lazymins[v];
    int b = lazymaxes[v];
    b = max(b,c);
    lazymins[v] = a;
    lazymaxes[v] = b;
}

void push(int v, int tl, int tr) {
    
    if (tl<tr) {
        lazymergemin(2*v,lazymins[v]);
        lazymergemin(2*v+1,lazymins[v]);
        lazymergemax(2*v,lazymaxes[v]);
        lazymergemax(2*v+1,lazymaxes[v]);
        //push(2*v,tl,(tl+tr)/2);
        //push(2*v+1,(tl+tr)/2+1,tr);
    }
    mergemin(v,lazymins[v]);
    mergemax(v,lazymaxes[v]);
    lazymins[v] = INF;
    lazymaxes[v] = -INF;

}

void maximize(int v, int l, int r, int tl, int tr, int value) {
    //if (tr<=15) cout << "maximizing " << l <<" " << r <<" " << tl <<" " << tr <<" " << value << endl;
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemax(v,value);
        if (tl<tr) {
            lazymergemax(2*v,value);
            lazymergemax(2*v+1,value);
        }
        return;
    }
    int m = (tl+tr)/2;
    maximize(2*v,l,r,tl,m,value);
    maximize(2*v+1,l,r,m+1,tr,value);
}

void minimize(int v, int l, int r, int tl, int tr, int value) {
    //if (tr<=15) cout << "minimizing " << l <<" " << r <<" " << tl <<" " << tr <<" " << value << endl;
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemin(v,value);
        if (tl<tr) {
            lazymergemin(2*v,value);
            lazymergemin(2*v+1,value);  
        }
        //cout << "merged minimum " << v <<" " << value <<" " << mins[v] <<" " << maxes[v] << endl;
        return;
    }
    int m = (tl+tr)/2;
    minimize(2*v,l,r,tl,m,value);
    minimize(2*v+1,l,r,m+1,tr,value);
}

int query(int v, int l, int r, int tl, int tr, int value) {
    push(v,tl,tr);
    if (l>tr || r<tl) {
        return INF;
    }
    if (l<=tl && tr<=r) {
        int ans = value;
        ans = min(ans,mins[v]);
        ans = max(ans,maxes[v]);
        //cout << "ending query " << l <<" " << r <<" " << value <<" " << mins[v] <<" " << maxes[v] <<" " << ans << endl;
        return ans;
    }
    int m = (tl+tr)/2;
    return min(query(2*v,l,r,tl,m,value),query(2*v+1,l,r,m+1,tr,value));
    
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0; i<sz; i++) {
        mins[i] = INF;
        maxes[i] = -INF;
        lazymins[i] = INF;
        lazymaxes[i] = -INF;
    }
    for (int i=0; i<k; i++) {
        if (op[i]==1) {
            maximize(1,left[i],right[i],0,2097151,height[i]);
            //for (int j=left[i]; j<=right[i]; j++) {
            //    mergemax(j+2097152,height[i]);
            //}
        }
        else {
            assert(op[i]==2);
            minimize(1,left[i],right[i],0,2097151,height[i]);
            //for (int j=left[i]; j<=right[i]; j++) {
            //    mergemin(j+2097152,height[i]);
            //}
        }
    }
    for (int i=0; i<n; i++) {
        int ans = query(1,i,i,0,2097151,0);
        finalHeight[i] = ans;
    }

    return;
}

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