Cod sursa(job #2016100)

Utilizator dementorrDementhor dementorr Data 28 august 2017 16:40:49
Problema Hotel Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <stdio.h>
#include <math.h>

typedef struct {
  int max;
  int stg;
  int dr;
  int de_updatat;
} batog;

int n, m;
int sqrt_n;

int v[100000];
batog w[4000];

void update_interval (int nr) {
  int stg = 0, dr = 0, max = 0;
  int i;
  for (i = (nr - 1) * sqrt_n + 1; i <= nr * sqrt_n; i++)
    if (v[i] == 1)
      stg++;
    else
      break;

  for (i = nr * sqrt_n; i >= (nr - 1) * sqrt_n + 1; i--)
    if (v[i] == 1)
      dr++;
    else
      break;

  int max_p = 0;
  for (i = (nr - 1) * sqrt_n + 1; i <= nr * sqrt_n; i++)
    if (v[i] == 1)
      max_p++;
    else {
      if (max < max_p) max = max_p;
      max_p = 0;
    }
  if (max < max_p) max = max_p;

  w[nr].stg = stg;
  w[nr].dr = dr;
  w[nr].max = max;
  w[nr].de_updatat = 0;
}

void de_update_intervale (int nr) {
  int i;
  for (i = (nr - 1) * sqrt_n + 1; i <= nr * sqrt_n; i++)
    v[i] = w[nr].max;
}

void update (int left, int right, int value) {
  int first_interval = left / sqrt_n + 1; if (left % sqrt_n == 0) first_interval--;
  int last_interval = right / sqrt_n + 1; if (right % sqrt_n == 0) last_interval--;

  if (w[first_interval].de_updatat == 1) {
    de_update_intervale (first_interval);
    update_interval (first_interval);
  }

  if (w[last_interval].de_updatat == 1) {
    de_update_intervale (last_interval);
    update_interval (last_interval);
  }

  int i;
  // daca e acelasi interval, terminam repede
  if (first_interval == last_interval) {
    for (i = left; i <= right; ++i)
      v[i] = value;
    update_interval (first_interval);
    return;
  }

  // mergem pana la primul interval
  for (i = left; i < first_interval * sqrt_n + 1; i++)
    v[i] = value;

  // mergem din interval in interval pana la ultimul - 1;
  for (i = first_interval + 1; i <= last_interval - 1; i++) {
    if (value == 1) {
      w[i].max = sqrt_n;
      w[i].stg = sqrt_n;
      w[i].dr = sqrt_n;
      w[i].de_updatat = 1;
    } else {
      w[i].max = 0;
      w[i].stg = 0;
      w[i].dr = 0;
      w[i].de_updatat = 1;
    }
  }

  // mergem de la ultimul - 1, pana unde trebuie
  for (i = (last_interval - 1) * sqrt_n + 1; i <= right; i++)
    v[i] = value;

  // updatam intervalele din capete
  update_interval (first_interval);
  update_interval (last_interval);
}

int query () {
  int max = w[1].max;
  int max_p = w[1].dr;
  
  int i;
  for (i = 2; i <= n / sqrt_n + 1; i++){
    if (max < w[i].max)
      max = w[i].max;

    if (w[i].max == sqrt_n)
      max_p += sqrt_n;
    else
      max_p += w[i].stg;

    if (max < max_p)
      max = max_p;

    if (w[i].max != sqrt_n)
      max_p = w[i].dr;
  }
  
  return max;
}

int main(){
  freopen ("hotel.in", "r", stdin);
  freopen ("hotel.out", "w", stdout);

  scanf ("%d %d\n", &n, &m);
  sqrt_n = sqrt(n);
  
  int i;
  for (i = 1; i <= n; ++i) {
    v[i] = 1;

    if (i <= sqrt_n + 1) {
      w[i].max = sqrt_n;
      w[i].stg = sqrt_n;
      w[i].dr = sqrt_n;
      w[i].de_updatat = 0;
    }
  }
  
  for (i = 0; i < m; ++i) {
    int op;
    scanf ("%d", &op);

    if (op == 1) {
      int left, right, add;
      scanf ("%d %d", &left, &add);
      right = left + add - 1;

      //printf ("update %d %d 0\n", left, right);
      update (left, right, 0);
    } else if (op == 2) {
      int left, right, add;
      scanf ("%d %d", &left, &add);
      right = left + add - 1;

      //printf ("update %d %d 1\n", left, right);
      update (left, right, 1);
    } else if (op == 3) {
      
      printf ("%d\n", query());
    }

    /*
    int j;
      
    for (j = 1; j <= n; ++j)
      printf ("%d ", v[j]);
    printf ("\n");

    for (j = 1; j <= n / sqrt_n + 1; ++j)
      printf ("%d => %d %d %d %d\n", j, w[j].stg, w[j].dr, w[j].max, w[j].de_updatat);
    printf ("\n");
    */
  }

  return 0;
}