Cod sursa(job #3288838)

Utilizator ItsHezovPahonie George Alessio ItsHezov Data 24 martie 2025 14:24:41
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
using namespace std;
ifstream cin("hotel.in");
ofstream cout("hotel.out");
const int mxN = 1e5;
struct node{int sum=0, pref, suf, flag;}A[4*mxN+1];
void printInfo(int node, int st, int dr)
{
     cout << "st = " << st << " dr = " << dr << '\n';
     cout << "sum = " << A[node].sum << '\n';
     cout << "pref = " << A[node].pref << ' ' << " suf = " << A[node].suf << '\n';
     cout << "flag = " << A[node].flag << '\n';
}
void build(int node, int st ,int dr)
{
    if(st == dr)
    {
        A[node] = {1,1,1,0};
        return;
    }
    int mid = (st + dr) / 2;
    build(2*node,st,mid);
    build(2*node+1,mid+1,dr);
    int val = A[2*node].sum + A[2*node+1].sum;
    A[node] = {val,val,val,0};
}
void update(int node , int st, int dr, int a , int b, int val)
{
    if(a<=st && dr <= b)
    {
        if(val == 1) // se ocupa intervalul.
            A[node] = {0,0,0,1};
        if(val == 0) // se elibera intervalul
        {
            int len = dr - st + 1;
            A[node] = {len,len,len,2};
        }
        //printInfo(node,st,dr);
        return;
    }
    int mid = (st + dr) / 2;
    int lenSt = mid - st + 1, lenDr = dr - mid;
    if(A[node].flag == 1)
        A[2*node] = A[2*node+1] = {0,0,0,1};
    if(A[node].flag == 2)
    {
        A[2*node] = {lenSt,lenSt,lenSt, 2};
        A[2*node+1] = {lenDr,lenDr,lenDr,2};
    }
    if(a<=mid)
        update(2*node,st,mid,a,b,val);
    if(b>mid)
        update(2*node+1,mid+1,dr,a,b,val);
    // dam update la intervalul combinat
    A[node].pref = A[2*node].pref;
    if(A[node].pref == lenSt)
        A[node].pref += A[2*node+1].pref;
    A[node].suf = A[2*node+1].suf;
    if(A[node].suf == lenDr)
        A[node].suf += A[2*node].suf;
    A[node].sum = max(A[2*node].sum, A[2*node+1].sum);
    A[node].sum = max(A[node].sum, A[2*node].suf + A[2*node+1].pref);
    //printInfo(node,st,dr);
}
int main()
{
    int n , m;
    cin >> n >> m;
    build(1,1,n);
    for(int i = 1;i<=m;i++)
    {
        //cout << "QUERY :";
        int op; cin >> op;
        if(op == 1)
        {
            int a , b;
            cin >> a >> b;
            update(1,1,n,a,a + b - 1,1);
        }
        if(op == 2)
        {
            int a, b;
            cin >> a >> b;
            update(1,1,n,a,a + b - 1,0);
        }
        if(op == 3)
        {
           cout << A[1].sum << '\n';
        }
    }
    return 0;
}