Cod sursa(job #1045131)

Utilizator smaraldaSmaranda Dinu smaralda Data 30 noiembrie 2013 22:04:32
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

const int NMAX = 132000;
int lmax[3 * NMAX + 10], seqLeft[3 * NMAX + 10], seqRight[3 * NMAX + 10], room[3 * NMAX + 10];

inline int max3 (int a, int b, int c) {
    int res = a;
    if(b > res) res = b;
    if(c > res) res = c;
    return res;
}

void updateRoom (int node, int left, int right) {
    int val;
    if(room[node] == 1)
        val = 0;
    else
        val = right - left + 1;
    lmax[node] = seqLeft[node] = seqRight[node] = val;
}



void update (int node, int left, int right, int a, int b, int val) {
    if(left >= a && right <= b) {
        room[node] = val;
        updateRoom(node,left,right);
        return;
    }

    int leftSon = node * 2, rightSon = node * 2 + 1, mid = (left + right) / 2;

    if(lmax[node] == 0 || lmax[node] == right - left + 1) {
        room[node] = room[leftSon] = room[rightSon] = lmax[node] == 0;
        updateRoom(leftSon, left, mid);
        updateRoom(rightSon, mid + 1, right);
    }

    if(a <= mid)
        update(leftSon, left, mid, a, b, val);
    if(b > mid)
        update(rightSon, mid + 1, right, a, b, val);

    seqLeft[node] = lmax[leftSon] == mid - left + 1 ? lmax[leftSon] + seqLeft[rightSon] : seqLeft[leftSon];
    seqRight[node] = lmax[rightSon] == right - mid ? lmax[rightSon] + seqRight[leftSon] : seqRight[rightSon];

    lmax[node] = max3(lmax[leftSon], lmax[rightSon], seqRight[leftSon] + seqLeft[rightSon]);
}

int main() {
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    int p2, n, i, p, c, a, b;

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

    update(1,1,n,1,n,0);

    for(i = 1; i <= p; i++) {
        scanf("%d",&c);
        if(c == 3) {
            printf("%d\n",lmax[1]);
            continue;
        }

        scanf("%d%d",&a,&b);
        if(c == 1)
            update(1,1,n,a, a + b - 1, 1);
        if(c == 2)
            update(1,1,n,a, a + b - 1, 0);
        }

    return 0;
}