Cod sursa(job #3264205)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 18 decembrie 2024 23:00:00
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>

#define MAXN 100001
#define MAXP 200001

#define MAX(a, b) ((a)>(b)?(a):(b))

int n, p;

struct segtree{
private:
  struct node{
    int max;
    int st;
    int dr;

    node add(const node other, int lenst, int lendr){
        node result = {0, 0, 0};

        if(this->st == lenst){
          result.st = this->st + other.st;
        }
        else
          result.st = this->st;

        if(other.dr == lendr){
          result.dr = other.dr + this->dr;
        }
        else result.dr = other.dr;

        result.max = MAX(this->max, other.max);
        if(result.st!=lenst+lendr){
          result.max = MAX(result.max, MAX(result.dr, result.st));
        }
        else
          result.max = result.st;

        result.max = MAX(result.max, this->dr+other.st);
      return result;
    }
  };
  int n;
  node aint[4*MAXN];
  char lazy[4*MAXN];

  void setNode(int node, int s, int d, int val){
    if(val==1){
      aint[node] = {0, 0, 0};
    }
    else{
      aint[node] = {d-s+1, d-s+1, d-s+1};
    }
    lazy[node] = val+1;
  }

  void updateLazy(int node, int s, int d){
    if(!lazy[node])return;

    int m = (s+d)/2;
    setNode(node*2, s, m, lazy[node]-1);
    setNode(node*2+1, m+1, d, lazy[node]-1);
    lazy[node] = false;
  }

  void update(int node, int s, int d, int a, int b, int val){
    if(a<=s && d<=b){
      setNode(node, s, d, val);
    }
    else{
      updateLazy(node, s, d);
      int m = (s+d)/2;
      if(a<=m) update(node*2, s, m, a, b, val);
      if(b>m) update(node*2+1, m+1, d, a, b, val);

      aint[node] = aint[node*2].add(aint[node*2+1], (m-s+1), (d-m));
    }
  }

public:
  void update(int a, int b, int val){
    update(1, 0, n-1, a, b, val);
  }
  int query(){
    return aint[1].max;
  }
  void init(int n){
    this->n = n;
  }
};

segtree aint;

int main(){
  freopen("hotel.in", "r", stdin);
  freopen("hotel.out", "w", stdout);
  scanf("%d%d", &n, &p);
  aint.init(n);
  aint.update(0, n-1, 2);
  for(int i=0; i<p; i++){
    int type, a, b;
    scanf("%d", &type);
    if(type==3){
      printf("%d\n", aint.query());
    }
    else{
      scanf("%d%d", &a, &b);
      a--;
      aint.update(a, a+b-1, type);
    }
  }

  return 0;
}