Cod sursa(job #2073477)

Utilizator flibiaVisanu Cristian flibia Data 23 noiembrie 2017 11:06:47
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>
#define L 2*pos
#define R 2*pos+1

using namespace std;

ifstream in("hotel.in");
ofstream out("hotel.out");

struct lol{
	int l, r;
};

int n, m, p, l, r, c, lazy[800100];
lol h[800100];

void update(int st, int dr, int pos, int l, int r, int val){
	int mid = (st + dr) >> 1;
	int f;
	if(lazy[pos] != 0){
		f = (lazy[pos] >= 1 ? 1 : 0);
		h[pos].l = (dr - st + 1) * f;
		h[pos].r = (dr - st + 1) * f;
		if(st != dr){
			lazy[L] += lazy[pos];
			lazy[R] += lazy[pos];
		}
		lazy[pos] = 0;
	}
	if(dr < l || st > r || st > dr)
		return;
	if(l <= st && dr <= r){
		f = (val >= 1 ? 1 : 0);
		h[pos].l = (dr - st + 1) * f;
		h[pos].r = (dr - st + 1) * f;
		if(st != dr){
			lazy[L] += val;
			lazy[R] += val;
		}
	//	cout << "upd " << st << ' ' << dr << ' ' << h[pos].l << ' ' << h[pos].r << '\n';
		return;
	}
	update(st, mid, L, l, r, val);
	update(mid+1, dr, R, l, r, val);
//	cout << "new " << st << ' ' << dr << ' ' << h[pos].l << ' ' << h[pos].r << ' ';
	//if(st != dr){
	
	h[pos].l = h[L].l + (h[L].l == (mid - st + 1)) * h[R].l;
	h[pos].r = h[R].r + (h[R].r == (dr - mid)) * h[L].r;
	//}
	//if(!h[pos].l || !h[pos].r)
		//h[pos].l = h[pos].r = 0;
//	cout << h[pos].l << ' ' << h[pos].r  << ' ' << '\n';
}

void afish(int st, int dr, int pos){
	if(st == dr){
		cout << st << ' ' << dr << ' ' << h[pos].l << ' ' << h[pos].r << '\n';
		return;
	}
	int mid = (st + dr) >> 1;
	afish(st, mid, L);
	afish(mid+1, dr, R);
}

int main(){
	in >> n >> m;
	update(1, n, 1, 1, n, 1);
//	cout << '\n';
	for(int i = 1; i <= m; i++){
		in >> c;
		if(c == 1){
			in >> l >> r;
			update(1, n, 1, l, l + r - 1, -1);
		}
		if(c == 2){
			in >> l >> r;
			update(1, n, 1, l, l + r - 1, 1);
		}
    	if(c == 3)
			out << max({h[2].r + h[3].l, h[1].r, h[1].l}) << '\n';
	//	cout << "\n";
	}
//	afish(1, n, 1);
	return 0;
}