Cod sursa(job #1048747)

Utilizator harababurelPuscas Sergiu harababurel Data 6 decembrie 2013 12:50:49
Problema Hotel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
//nu merge
#include <iostream>
#include <fstream>
#include <iomanip>
#define nmax 100005
#define hmax 4*nmax
using namespace std;
 
int n, p, op, a, b;
int H[hmax], L[hmax], R[hmax], lazy[hmax];

int max(int a, int b, int c) {
	int ret = a;
	ret = b > ret ? b : ret;
	ret = c > ret ? c : ret;
	return ret;
}
 
void sendLaziness(int node, int lo, int hi) {
    int mid = (lo + hi) >> 1;
    if(lazy[node] == 1) {   //vin turisti -> se pune 1
        H[2*node] = 0;
        H[2*node+1] = 0;
    }
    if(lazy[node] == 2) {   //pleaca turisti -> se pune 0
        H[2*node] = mid - lo + 1;
        H[2*node+1] = hi - mid;
	
    }
    
    L[2*node] = H[2*node];
    R[2*node] = H[2*node];
    L[2*node+1] = H[2*node+1];
    R[2*node+1] = H[2*node+1];

    lazy[2*node] = lazy[node];
    lazy[2*node+1] = lazy[node];
 
    lazy[node] = 0;
}
 
void update(int node, int lo, int hi, int a, int b, int val) {
    if(a <= lo && hi <= b) {
        if(val == 1) H[node] = 0;
        else H[node] = hi - lo + 1;
 
        L[node] = H[node];
        R[node] = H[node];
        lazy[node] = val;
        return;
    }
 
    int mid = (lo + hi) >> 1;
    if(lazy[node]) sendLaziness(node, lo, hi);
 
    if(a <= mid) update(2*node, lo, mid, a, b, val);
    if(mid < b)  update(2*node+1, mid+1, hi, a, b, val);
 
    H[node] = max(H[2*node], H[2*node+1], R[2*node] + L[2*node+1]);
 
    L[node] = L[2*node];
    if(L[2*node] == mid - lo + 1) L[node] += L[2*node+1];
 
    R[node] = R[2*node+1];
    if(R[2*node+1] == hi - mid) R[node] += R[2*node];
}
 
int query(int node) {
	return H[node];
}

void build(int node, int lo, int hi) {
	if(lo == hi) {
		H[node] = L[node] = R[node] = 1;
		return;
	}

	int mid = (lo + hi) >> 1;
	build(2*node, lo, mid);
	build(2*node+1, mid+1, hi);

	H[node] = H[2*node] + H[2*node+1];
	L[node] = L[2*node] + L[2*node+1];
	R[node] = R[2*node] + R[2*node+1];
}
 
int main() {
    ifstream f("hotel.in");
    ofstream g("hotel.out");
 
    f>>n>>p;

    build(1, 1, n);
    for(int i=1; i<=p; i++) {
        f>>op;
        if(op == 1) {
            f>>a>>b;
            update(1, 1, n, a, a+b-1, 1);
        }
        if(op == 2) {
            f>>a>>b;
            update(1, 1, n, a, a+b-1, 2);
        }
        if(op == 3) cout<<query(1)<<"\n";
	
    }
 
    return 0;
}