Cod sursa(job #831172)

Utilizator lehman97Dimulescu David lehman97 Data 8 decembrie 2012 11:15:46
Problema Hotel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f=fopen("hotel.in","r");
FILE *g=fopen("hotel.out","w");
int v[800000],n,p,i,c,a,nr,maxim,k=0;

int mx(int a ,int b)
{
  if(a>b)return a;else return b;
}

void update(int l,int r, int pi, int pf, int val ,int nod)
{
  int m=(l+r)/2;
  if(l==r) {v[nod]+=val;return;}
  else
  {
  if(pi<=m) update(l,m,pi,pf,val,2*nod);
  if(m<pf) update(m+1,r,pi,pf,val,2*nod+1);
  }
  v[nod]=v[2*nod]+v[2*nod+1];
}

void query(int l, int r,int nod)
{
    int m=(l+r)/2,s1,s2;
    if (l==r)
        {
        if(v[nod]==1)k++;
        if(k>maxim) maxim=k;
        if(v[nod]==0)k=0;
        return;
        }
    else
    {
     query(l,m,2*nod);
     query(m+1,r,2*nod+1);
    }
}

int main()
{
    fscanf(f,"%d%d",&n,&p);
    for(i=1;i<=n;i++)
        update(1,n,i,i,1,1);
    for(i=1;i<=p;i++)
      {
        fscanf(f,"%d",&c);
        switch(c)
        {
          case 1:{fscanf(f,"%d%d",&a,&nr);update(1,n,a,nr+a-1,-1,1);break;}
          case 2:{fscanf(f,"%d%d",&a,&nr);update(1,n,a,nr+a-1,1,1);break;}
          case 3:{maxim=0;k=0;query(1,n,1);if(k>maxim)maxim=k;fprintf(g,"%d\n",maxim);break;}
        }
      }
fclose(g);
return 0;
}