Cod sursa(job #2908134)

Utilizator matthriscuMatt . matthriscu Data 1 iunie 2022 16:55:03
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
	
using namespace std;
	
ifstream in("hotel.in");
	
ofstream out("hotel.out");
	
const int nmax= 262144;
	
struct str {
	
    int a, b, c;
	
};
	
str v[nmax+1];
	
void update( int x, int l, int r, int a, int b, int z ) {
	
    if (a <= l && r <= b) {
	
        if (z == 1) {
	
            v[x].a = v[x].b = v[x].c = 0;
	
        } else {
	
            v[x].a = v[x].b = v[x].c = r - l + 1;
	
        }
	
    } else if (a <= r && b >= l) {
	
        if (v[x].a == 0) {
	
            v[2 * x].a = v[2 * x].b = v[2 * x].c = v[2 * x + 1].a = v[2 * x + 1].b = v[2 * x + 1].c = 0;
	
        } else if (v[x].a == r - l + 1) {
	
            v[2 * x].a = v[2 * x].b = v[2 * x].c = (l + r) / 2 - l + 1;
	
            v[2 * x + 1].a = v[2 * x + 1].b = v[2 * x + 1].c = r - (l + r) / 2;
	
        }
	
        update(2 * x, l, (l + r) / 2, a, b, z);
	
        update(2 * x + 1, (l + r) / 2 + 1, r, a, b, z);
	
        v[x].b= v[2 * x].b;
	
        v[x].c= v[2 * x + 1].c;
	
        if (v[x].b == (l + r) / 2 - l + 1) {
	
            v[x].b += v[2 * x + 1].b;
	
        }
	
        if (v[x].c == r - (l + r) / 2) {
	
            v[x].c += v[2 * x].c;
	
        }
	
        v[x].a = max(max(v[2 * x].a, v[2 * x + 1].a), v[2 * x].c + v[2 * x + 1].b);
	
    }
	
}
	
int main( ) {
	
    int n, t;
	
    in >> n >> t;
	
    update(1, 1, n, 1, n, 2);
	
    for (int cnt = 1; cnt <= t; ++cnt) {
	
        int z;
	
        in >> z;
	
        if ( z == 3 ) {
	
            out << v[1].a << "\n";
	
        } else {
	
            int x, y;
	
            in >> x >> y;
	
            update(1, 1, n, x, x + y - 1, z);
	
        }
	
    }
	
    return 0;
	
}