Cod sursa(job #2596519)

Utilizator victorzarzuZarzu Victor victorzarzu Data 9 aprilie 2020 20:04:13
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("hotel.in");
ofstream g("hotel.out");
int n, p;
int a, b;
struct node
{
  int lazy, length, l, r, m;
} arb[4 * 100005];


void build(int nod, int st, int dr)
{
  if(st == dr)
  {
    arb[nod].length = arb[nod].l = arb[nod].r = arb[nod].m = 1;
    arb[nod].lazy = 0;
    return;
  }

  int mid = (st + dr) / 2;
  build(2 * nod, st, mid);
  build(2 * nod + 1, mid + 1, dr);
  
  arb[nod].length = arb[2 * nod].length + arb[2 * nod + 1].length;
  arb[nod].l = arb[2 * nod].length + arb[2 * nod + 1].length;
  arb[nod].r = arb[2 * nod].length + arb[2 * nod + 1].length;
  arb[nod].m = max(arb[nod].m, arb[2 * nod].length + arb[2 * nod + 1].length);
}

void add(int nod, int st, int dr,int val)
{
  if(arb[nod].lazy)
  {
    arb[nod].m += (dr - st + 1) * arb[nod].lazy;
    arb[nod].l += (dr - st + 1) * arb[nod].lazy;
    arb[nod].r += (dr - st + 1) * arb[nod].lazy;

    if(st != dr)
      {
        arb[2 * nod].lazy += arb[nod].lazy;
        arb[2 * nod + 1].lazy += arb[nod].lazy;
      }
    arb[nod].lazy = 0;
  }

  if(st > dr || st > b || dr < a)
    return;
  
  if(a <= st && dr <= b)
  {   
    arb[nod].m += (dr - st + 1) * val;
    arb[nod].l += (dr - st + 1) * val;
    arb[nod].r += (dr - st + 1) * val;

    if(st != dr)
    {
      arb[2 * nod].lazy += val;
      arb[2 * nod + 1].lazy += val;
    }
    return;
  }

  int mid = (st + dr) / 2;
  add(2 * nod, st, mid, val);
  add(2 * nod + 1, mid + 1, dr, val);

  arb[nod].m = max(arb[2 * nod].r + arb[2 * nod + 1].l, max(arb[2 * nod].m, arb[2 * nod + 1].m));
  arb[nod].l = arb[2 * nod].l;
  arb[nod].r = arb[2 * nod + 1].r;

  if(arb[2 * nod].l == arb[2 * nod].length)
  {
    arb[nod].m = max(arb[nod].m, arb[2 * nod].length + arb[2 * nod + 1].l);
    arb[nod].l = arb[2 * nod].length + arb[2 * nod + 1].l;
  }

  if(arb[2 * nod + 1].r == arb[2 * nod + 1].length)
  {
    arb[nod].m = max(arb[nod].m, arb[2 * nod + 1].length + arb[2 * nod].r);
    arb[nod].r = arb[2 * nod + 1].length + arb[2 * nod].r;
  }
}

void Read()
{
  f>>n>>p;
  build(1, 1, n);
  int x, y, z;
  for(int i = 1;i <= p;++i)
  {
    f>>x;
    if(x == 3)
      g<<arb[1].m<<'\n';
    else
    {
      f>>y>>z;
      a = y;
      b = y + z - 1;
      if(x == 1)
        add(1, 1, n, -1);
      else
        add(1, 1, n, 1);
    }
  }
}

int main()
{
  Read();
  return 0;
}