Submission #1062891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062891		anango	Wall (IOI14_wall)	C++17	0 / 100	3075 ms	78928 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 push(int v, int tl, int tr) {
    if (tl<tr) {
        mergemin(2*v,mins[v]);
        mergemax(2*v,maxes[v]);
        mergemin(2*v+1,mins[v]);
        mergemax(2*v+1,maxes[v]);
        push(2*v,tl,(tl+tr)/2);
        push(2*v+1,(tl+tr)/2+1,tr);
    }
}

void maximize(int v, int l, int r, int tl, int tr, int value) {
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemax(v,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) {
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemin(v,value);
        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: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39