Cod sursa(job #1712931)

Utilizator valentin50517Vozian Valentin valentin50517 Data 4 iunie 2016 12:07:34
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
struct nod{
	int st,dr,b,lazy;
} ARB[400100];
int st,dr,VAL;
 
void add(int nod,int l,int r){
	
	if(ARB[nod].lazy != 0){
		ARB[nod].st += (r-l+1)*ARB[nod].lazy;
		ARB[nod].dr += (r-l+1)*ARB[nod].lazy;
		ARB[nod].b  += (r-l+1)*ARB[nod].lazy;
		if(l != r) ARB[2*nod].lazy +=ARB[nod].lazy, ARB[2*nod+1].lazy += ARB[nod].lazy;
		ARB[nod].lazy = 0;
	}
	
	if(dr < l || st > r) return;
	if(l >= st && dr >= r){
		ARB[nod].st += (r-l+1)*VAL;
		ARB[nod].dr += (r-l+1)*VAL;
		ARB[nod].b  += (r-l+1)*VAL;
		if(l != r) ARB[2*nod].lazy += VAL, ARB[2*nod+1].lazy += VAL;
		return;
	}
	
	int mid = (l+r)/2;
	add(2*nod,l,mid);
	add(2*nod+1,mid+1,r);         
	ARB[nod].dr = (ARB[2*nod+1].dr == r-mid) ? ARB[2*nod+1].dr + ARB[2*nod].dr : ARB[2*nod+1].dr;
	ARB[nod].st = (ARB[2*nod].st == mid-l+1) ? ARB[2*nod+1].st + ARB[2*nod].st : ARB[2*nod].st;
	ARB[nod].b = max(ARB[2*nod].b,max(ARB[2*nod+1].b,ARB[2*nod].dr + ARB[2*nod+1].st));
}
 
int N,M,c;
int main(){
	fin >> N >> M;
	st = 1;dr = N;VAL = 1;
	add(1,1,N);
	while(M--){
		fin >> c;
		if(c != 3){
			VAL = (c==1)?-1:1;
			fin >> st >> dr;
			dr = st+dr-1; 
			add(1,1,N);
		}else fout << ARB[1].b << '\n';
	}
}