Cod sursa(job #2072752)

Utilizator flibiaVisanu Cristian flibia Data 22 noiembrie 2017 10:33:28
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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) * lazy[pos];
		h[pos].r = (dr - st + 1) * lazy[pos];
		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;
		}
		return;
	}
	update(st, mid, L, l, r, val);
	update(mid+1, dr, R, l, r, val);
	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;
}

int main(){
	in >> n >> m;
	update(1, n, 1, 1, n, 1);
	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';
	}
	return 0;
}