Cod sursa(job #3160282)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 23 octombrie 2023 17:12:20
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.15 kb
#include <bits/stdc++.h>

using namespace std;

// struct Data {};
// struct Lazy {};

struct xdata {
    int left, right, ans;
    int size;
};

template <typename Data , typename Lazy>
struct SegTreeOperations {
	static Data mergeData(Data left, Data right) { 
        Data ret;
        if (left.left == left.size) {
            ret.left = left.size + right.left;
        }
        else ret.left = left.left;
        if (right.right == right.size) {
            ret.right = right.right + left.right;
        }
        else ret.right = right.right;
        ret.size = left.size + right.size;
        ret.ans = max({left.ans , right.ans , left.right + right.left});

        return ret;
    }
	static Data addLazy(Data current, Lazy tag, int left, int right) { 
        Data rez;
        rez.size = current.size;
        if (tag == -1) {
            rez.ans = rez.left = rez.right = current.size;

        }
        else if (tag == 1)
        {
            rez.ans = rez.left = rez.right = 0;
        }
        return rez;
    }
	static Lazy mergeLazy(Lazy old_tag, Lazy new_tag) {
		Lazy ret = new_tag;
        return ret;
	}

	static Data zeroData() { return {0,0,0,1}; }
	static Lazy zeroLazy() { return 0; }
    static Data initData() { return {1,1,1,1}; }
};

/* struct STO2 {
	;
}; */

template < typename D >
struct vec {
	D* data;
}; // -> vec<int>

template < typename Data, typename Lazy, typename STO /* SegTreeOperations */ > 
struct SegTree {
	vector<Data> data;
	vector<Lazy> lazy;

	// static const int zero_data = STO::zeroData();

	int offset;
	int next_power_of_2(int n) {
		int p = 1;
		while(p <= n) p *= 2;
		return p;
	}

	SegTree(int n) {
		offset = next_power_of_2(n);
		data.resize(2 * offset, STO::zeroData());
		lazy.resize(2 * offset, STO::zeroLazy());
	}

	void push_lazy(int node, int l, int r) {
		if(lazy[node] == STO::zeroLazy()) return;
		data[node] = STO::addLazy(data[node], lazy[node], l, r);
		
		if(node < offset) {
			lazy[2 * node] = STO::mergeLazy(lazy[2 * node], lazy[node]);
			lazy[2 * node + 1] = STO::mergeLazy(lazy[2 * node + 1], lazy[node]);
		}

		lazy[node] = STO::zeroLazy();
		return;
	}

	void _update(int node, int l, int r, int gl, int gr, Lazy tag) {
		push_lazy(node, l, r);
		if(l > gr || r < gl) return;

		if(gl <= l && r <= gr) {
			lazy[node] = STO::mergeLazy(lazy[node], tag);
			push_lazy(node, l, r);
			return;
		}

		int mid = (l + r) / 2;
		_update(2 * node, l, mid, gl, gr, tag);
		_update(2 * node + 1, mid + 1, r, gl, gr, tag);

		data[node] = STO::mergeData(data[2 * node], data[2 * node + 1]);
		return;
	}

	Data _query(int node, int l, int r, int gl, int gr) {
		push_lazy(node, l, r);
		if(l > gr || r < gl) return STO::zeroData();

		if(gl <= l && r <= gr) return data[node];
		
		int mid = (l + r) / 2;
		return STO::mergeData(_query(2 * node, l, mid, gl, gr), _query(2 * node + 1, mid + 1, r, gl, gr));
	}

	void update(int l, int r, Lazy tag) {
		_update(1, 0, offset - 1, l, r, tag);
	}

	Data query(int l, int r) {
		return _query(1, 0, offset - 1, l, r);
	}

	void print(int l, int r) {
		for(int pos = l; pos <= r; ++pos) {
			cerr << query(pos, pos).ans << ' ';
		}
		cerr << endl;
	}
};

int main() {
    freopen("hotel.in" , "r" , stdin);
    freopen("hotel.out" , "w" , stdout);
	// fara static
	// SegTreeOperations sto;
	// x = sto.mergeData(y, z);

	// cu static
	// x = SegTreeOperations::mergeData(y, z);

	// SegTree<int64_t, int64_t, SegTreeOperations> st(10);
	// SegTree<int64_t, int64_t, STO2> st2(10);]]

    int n, p; cin >> n >> p;
    SegTree < xdata , int , SegTreeOperations < xdata , int > > aint(n);

    for (int i = 1; i <= n; i++)
    {
        aint.update(i,i,-1);
    }

    while (p--)
    {
      //  aint.print(1, n);
        int c; cin >> c;
        if (c == 3) {
            cout << aint.query(1, n).ans << '\n';
        }
        else if (c == 2)
        {
            int i, m; cin >> i >> m;
            aint.update(i, i + m - 1, -1);
        }
        else {
            int i, m; cin >> i >> m;
            aint.update(i, i + m - 1, 1);
        }
    }

}