Cod sursa(job #2728810)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 23 martie 2021 18:51:13
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream f("hotel.in");
ofstream g("hotel.out");

struct data{
	int sum, pref, suff, ans;
} t[400001];

int N, P;

data combine(data l, data r){
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
    return res;
}

data make_data(int val){
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = max(0, val);
    return res;
}

data query(int v, int tl, int tr, int l, int r) {
    if(l > r) 
        return make_data(0);
    if(l == tl && r == tr) 
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(query(v * 2, tl, tm, l, min(r, tm)), query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}

void build(int v, int tl, int tr){
    if(tl == tr){
        t[v] = make_data(1);
    } else {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (tl == tr) {
        t[v] = make_data(add);
        return;
    } else {
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, l, min(r, tm), add);
        update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, add);
        t[v] = combine(t[v * 2], t[v * 2 + 1]);
    }
}

int main(){
	f >> N >> P;
	build(1, 1, N);

	while(P--){
		int op, x, y;
		f >> op;
		if(op == 3) g << query(1, 1, N, 1, N).ans << "\n";
		if(op == 1) {
			f >> x >> y;
			update(1, 1, N, x, x + y - 1, -1);
		}
		if(op == 2){
			f >> x >> y;
			update(1, 1, N, x, x + y - 1, 1);
		}
	}
}