Cod sursa(job #2073865)

Utilizator flibiaVisanu Cristian flibia Data 23 noiembrie 2017 19:40:48
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 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 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;
	}
	int mid = (st + dr) >> 1;
	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);
}

//void gene(){
//	int x, y, z, sz;
//	for(int i = 1; i <= m; i++){
//		x = rand() % 3 + 1;
//		out << x << ' ';
//		if(x == 1 || x == 2){
//			y = rand() % n + 1;
//			sz = n - y;
//			z = rand() % sz + (y + 1);
//			out << y << ' ' << z;
//		}
//		out << '\n';
//	}
//}

int main(){
	in >> n >> m;
//	gene();
	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;
}