Cod sursa(job #1908412)

Utilizator M.AndreiMuntea Andrei Marius M.Andrei Data 7 martie 2017 01:50:50
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f{ "hotel.in" };
ofstream q{ "hotel.out" };

struct arbore
{
   int val, st, dr;
   void reset(int value, int op)
   {
      if (op == 1) val = st = dr = 0;
      else val = st = dr = value;
   }
};

arbore arb[400010];

void build(int node, int start, int end)
{
   
   arb[node].reset(end - start + 1, 2);
   if (start == end) return;

   int mid = (end + start) / 2;
   build(node * 2, start, mid);
   build(node * 2 + 1, mid + 1, end);

}

void update(int node, int start, int end, int left, int right, int val)
{

   if (start > end || start > right || end < left) return;

   if (left <= start && end <= right)
   {
      arb[node].reset(end - start + 1, val);
      return;
   }

   int mid = (start + end) / 2;

   if (arb[node].val == 0) arb[node * 2].reset(0, 1), arb[node * 2 + 1].reset(0, 1);
   else if (arb[node].val == end - start + 1) arb[node * 2].reset(mid - start + 1, 2), arb[node * 2 + 1].reset(end - mid, 2);

   update(2 * node, start, mid, left, right, val);
   update(2 * node + 1, mid + 1, end, left, right, val);

   arb[node].val = max(max(arb[node * 2].val, arb[node * 2 + 1].val), arb[2 * node].dr + arb[2 * node + 1].st);
   
   arb[node].st = arb[node * 2].st;
   if (arb[node * 2].st == mid - start + 1) arb[node].st += arb[node * 2 + 1].st;
   
   arb[node].dr = arb[node * 2 + 1].dr;
   if (arb[node * 2 + 1].dr == end - mid) arb[node].dr += arb[node * 2].dr;

}


int main()
{
   int n, m;
   int c, start, contor;
   f >> n >> m;

   build(1, 1, n);

   for(;m--;)
   {
      f >> c;
      if (c == 3)
      {
         q << arb[1].val << "\n";
         continue;
      }
      f >> start >> contor;
      update(1, 1, n, start, start + contor - 1, c);
   }

   
   f.close();
   q.close();
   return 0;
}