Cod sursa(job #1524372)

Utilizator kassay_akosKassay Akos kassay_akos Data 13 noiembrie 2015 23:43:44
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <iostream>
#include <fstream>
using namespace std;

struct triint {
    int best, left, right ;
};
triint arb[500000] ;
int n,p,op;

void InitArb(int nodID, int start, int finish) ;
void Update(int nodID, int start, int finish, int from, int to);

inline int Maxim(int a, int b, int c) {
       if ( a > b ) {
            if (a > c ) return a;
            return c;
       }
       else {
            if (b > c) return b;
            return c;
       }
}

int main()
{
    freopen("hotel.in","r",stdin);
	freopen("hotel.out","w",stdout);

    scanf("%d%d",&n,&p);
    InitArb(1,1,n);

    int A,B;
    for(int i = 0; i<p; i++) {
        scanf("%d",&op);
        if (op==3) {
            printf("%i \n",arb[1].best);
        }
        else {
            scanf("%d%d",&A,&B);
            B = A+B-1;
            Update(1,1,n,A,B);
        }
    }
    return 0;
}


void InitArb(int nodID, int start, int finish) {
    arb[nodID].best = arb[nodID].left = arb[nodID].right = finish-start+1 ;
    if (start == finish) {
        return ;
    }
    int mid = (start + finish)/2 ;
    InitArb(nodID*2,start, mid);
    InitArb(nodID*2+1, mid+1, finish);
}

void Update(int nodID, int start, int finish, int from, int to) {
    if (finish < from || to < start) {
        return ;
    }
    int mid = (start+finish)/2;
    if (from <= start && finish <= to) {
        if (op==1) {
            arb[nodID].best = arb[nodID].left = arb[nodID].right = 0; }
        else {
            arb[nodID].best = arb[nodID].left = arb[nodID].right =  finish - start + 1; }
        return ;
    }

    if (arb[nodID].best == 0) {
        arb[nodID*2].best=arb[nodID*2].left=arb[nodID*2].right= 0;
        arb[nodID*2+1].best=arb[nodID*2+1].left=arb[nodID*2+1].right= 0;
    }
    if (arb[nodID].best == finish-start+1) {
        arb[nodID*2].best=arb[nodID*2].left=arb[nodID*2].right= mid-start+1;
        arb[nodID*2+1].best=arb[nodID*2+1].left=arb[nodID*2+1].right= finish-mid;
    }
    Update(nodID*2,start,mid,from,to);
    Update(nodID*2+1,mid+1,finish,from,to);

    arb[nodID].best = Maxim(arb[nodID*2].best, arb[nodID*2+1].best, arb[nodID*2].right + arb[nodID*2+1].left);
    arb[nodID].left = arb[nodID*2].left;
    arb[nodID].right = arb[nodID*2+1].right;

    if (arb[nodID].left == mid-start+1) {
        arb[nodID].left += arb[nodID*2+1].left;
    }
    if ( arb[nodID].right == finish - mid ){
        arb[nodID].right += arb[nodID*2].right ;
    }
}