Cod sursa(job #200385)

Utilizator hadesgamesTache Alexandru hadesgames Data 23 iulie 2008 18:18:35
Problema Hotel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
using namespace std;
#define FOR(i,a,b) for (typeof a i=a;i<=b;i++)
#define fori(it,v) for (typeof ((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define apopf pop_front
struct ceva{int v,st,dr;};
vector <ceva> arb;
void update1(int x,int p,int u,int i,int j)
{
	if (p>=i&&u<=j)
	{
		arb[x].st=0;
		arb[x].dr=0;
		arb[x].v=0;
		return ;
	}
	int m=(p+u)/2;
	if (i<=m)
		update1(2*x,p,m,i,j);
	if (j>m)
		update1(2*x+1,m+1,u,i,j);
	if (arb[2*x].st==m-p+1)
		arb[x].st=arb[2*x].st+arb[2*x+1].st;
	else
		arb[x].st=arb[2*x].st;
	if (arb[2*x+1].dr==u-m)
		arb[x].dr=arb[2*x].dr+arb[2*x+1].dr;
	else
		arb[x].dr=arb[2*x+1].dr;
	arb[x].v=max(arb[2*x].dr+arb[2*x+1].st,max(arb[x].st,arb[x].dr));
}
void update2(int x,int p,int u,int i,int j)
{
	if (p>=i&&u<=j)
	{
		arb[x].st=u-p+1;
		arb[x].dr=u-p+1;
		arb[x].v=u-p+1;
		return ;
	}
	int m=(p+u)/2;
	if (i<=m)
		update2(2*x,p,m,i,j);
	if (j>m)
		update2(2*x+1,m+1,u,i,j);
	if (arb[2*x].st==m-p+1)
		arb[x].st=arb[2*x].st+arb[2*x+1].st;
	else
		arb[x].st=arb[2*x].st;
	if (arb[2*x+1].dr==u-m)
		arb[x].dr=arb[2*x].dr+arb[2*x+1].dr;
	else
		arb[x].dr=arb[2*x+1].dr;
	arb[x].v=max(arb[2*x].dr+arb[2*x+1].st,max(arb[x].st,arb[x].dr));
}
void nou(int x,int p,int u)
{
	arb[x].v=u-p+1;
	arb[x].st=u-p+1;
	arb[x].dr=u-p+1;
	if (p!=u)
	{
		int m=(p+u)/2;
		nou(x*2,p,m);
		nou(x*2+1,m+1,u);
	}


}
int main()
{
	int x,y,c,n,p;
	ifstream in("hotel.in");
	ofstream out("hotel.out");
	in>>n>>p;
	arb.resize(2*n+3);
	nou(1,1,n);
	FOR(i,1,p)
	{
		in>>c;
		if (c==3)
			out<<arb[1].v<<'\n';
		else
		{
			in>>x>>y;
			if (c==1)
			{
				update1(1,1,n,x,x+y-1);
			}
			else
			{
				update2(1,1,n,x,x+y-1);
			
				fori(it,arb)
					printf("(%d %d %d)",it->v,it->st,it->dr);
			printf("\n\n");
			//	update2(1,1,n,x,x+y-1);
			}
		}
	}
	in.close();
	out.close();
	return 0;
}