Submission #1062867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062867		oscar1f	Wall (IOI14_wall)	C++17	100 / 100	1091 ms	91988 KiB

wall

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

struct som {
    int debInter,finInter,minInter,maxInter;
};

const int TAILLE_MAX=(1<<21),INFINI=1000*1000*1000;
int nbVal,nbReq;
som lazy[2*TAILLE_MAX];

void pushFlag(int pos) {
    if (lazy[pos].debInter!=lazy[pos].finInter) {
        for (int j=0;j<2;j++) {
            if (lazy[2*pos+j].maxInter<lazy[pos].minInter) {
                lazy[2*pos+j].minInter=lazy[pos].minInter;
                lazy[2*pos+j].maxInter=lazy[pos].minInter;
            }
            else if (lazy[2*pos+j].minInter>lazy[pos].maxInter) {
                lazy[2*pos+j].minInter=lazy[pos].maxInter;
                lazy[2*pos+j].maxInter=lazy[pos].maxInter;
            }
            else {
                lazy[2*pos+j].minInter=max(lazy[2*pos+j].minInter,lazy[pos].minInter);
                lazy[2*pos+j].maxInter=min(lazy[2*pos+j].maxInter,lazy[pos].maxInter);
            }
        }
        lazy[pos].minInter=0;
        lazy[pos].maxInter=INFINI;
    }
}

void init(int pos,int deb,int fin) {
    lazy[pos].debInter=deb;
    lazy[pos].finInter=fin;
    //cout<<pos<<" "<<deb<<" "<<fin<<endl;
    if (deb!=fin) {
        int mid=(deb+fin)/2;
        init(2*pos,deb,mid);
        init(2*pos+1,mid+1,fin);
    }
}

void modif(int pos,int deb,int fin,int typeModif,int valModif) {
    if (lazy[pos].debInter>fin or lazy[pos].finInter<deb) {
        pushFlag(pos);
    }
    else if (lazy[pos].debInter>=deb and lazy[pos].finInter<=fin) {
        if (typeModif==1) {
            lazy[pos].minInter=max(lazy[pos].minInter,valModif);
            lazy[pos].maxInter=max(lazy[pos].maxInter,valModif);
        }
        else {
            lazy[pos].minInter=min(lazy[pos].minInter,valModif);
            lazy[pos].maxInter=min(lazy[pos].maxInter,valModif);
        }
        pushFlag(pos);
    }
    else {
        pushFlag(pos);
        if (lazy[pos].debInter!=lazy[pos].finInter) {
            modif(2*pos,deb,fin,typeModif,valModif);
            modif(2*pos+1,deb,fin,typeModif,valModif);
        }
    }
}

int calcVal(int pos,int posVal) {
    pushFlag(pos);
    if (lazy[pos].debInter<=posVal and lazy[pos].finInter>=posVal) {
        if (lazy[pos].debInter!=lazy[pos].finInter) {
            return calcVal(2*pos,posVal)+calcVal(2*pos+1,posVal);
        }
        else {
            return lazy[pos].minInter;
        }
    }
    else {
        return 0;
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    nbVal=n;
    nbReq=k;
    init(1,0,nbVal-1);
    for (int i=0;i<nbReq;i++) {
        modif(1,left[i],right[i],op[i],height[i]);
        /*for (int j=0;j<nbVal;j++) {
            cout<<calcVal(1,j)<<" ";
        }
        cout<<endl;*/
    }
    for (int i=0;i<nbVal;i++) {
        finalHeight[i]=calcVal(1,i);
    }
    return;
}

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