Cod sursa(job #309558)

Utilizator SleepyOverlordPatcas Csaba SleepyOverlord Data 30 aprilie 2009 17:27:26
Problema Hotel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
//Code by Patcas Csaba
//Time complexity: O(m * log n)
//Space complexity: O(n)
//Method: Ai
//Working time: 1 hour 30 minutes

#include <stdio.h>
#include <ctype.h>
#include <vector>
#include <string> 
#include <set> 
#include <map> 
#include <iostream> 
#include <sstream> 
#include <numeric> 
#include <algorithm> 
#include <cmath> 
#include <queue> 
#include <bitset> 

using namespace std;

#define in_file "hotel.in"
#define out_file "hotel.out"

#define VI vector <int>
#define FORN(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define S size()
#define B begin() 
#define E end() 
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define ALL(x) x.begin(),x.end()
#define repeat do{ 
#define until(x) }while(!(x)); 

struct Tai
{
	int len, left, right;
};

int n, p;
vector <Tai> ai;

void build(int node, int down, int up)
{
	if (down==up)
	{
		ai[node].len= 1;
		ai[node].left= 1;
		ai[node].right= 1;
		return ;
	}
	
	int mid= (down + up) / 2;
	build(node * 2, down, mid);
	build(node * 2 + 1, mid + 1, up);

	ai[node].len= max(ai[node * 2].right + ai[node * 2 + 1].left, 
								max(ai[node * 2].len, ai[node * 2 + 1].len));
	ai[node].left= ai[node * 2].left;
	if (ai[node * 2].left == (mid - down + 1)) ai[node].left+= ai[node * 2 + 1].left;
	ai[node].right= ai[node * 2 + 1].right;
	if (ai[node * 2 + 1].right == (up - mid)) ai[node].right+= ai[node * 2].right;
}

void update(int node, int down, int up, int i, int j, int op)
{
	if (i<=down && up<=j)
	{
		if (op == 2)
		{
			ai[node].len= (up - down + 1);
			ai[node].left= (up - down + 1);
			ai[node].right= (up - down + 1);
		}
		else
		{
			ai[node].len= 0;
			ai[node].left= 0;
			ai[node].right= 0;
		}
		//return ;
	}

	if (down==up) return ;

	int mid= (down + up) / 2;
	if (i <= mid) update(node * 2, down, mid, i , j , op);
	if (mid + 1 <= j) update(node * 2 + 1, mid + 1, up, i , j , op);

	ai[node].len= max(ai[node * 2].right + ai[node * 2 + 1].left, 
		max(ai[node * 2].len, ai[node * 2 + 1].len));
	ai[node].left= ai[node * 2].left;
	if (ai[node * 2].left == (mid - down + 1)) ai[node].left+= ai[node * 2 + 1].left;
	ai[node].right= ai[node * 2 + 1].right;
	if (ai[node * 2 + 1].right == (up - mid)) ai[node].right+= ai[node * 2].right;
}

void debug(int node, int down, int up)
{
	cout<<down<<" "<<up<<" "<<ai[node].len<<endl;
	if (down<up)
	{
		int mid=(down+up)/2;
		debug(node * 2, down, mid);
		debug(node * 2 + 1, mid + 1, up);
	}
}

int main()
{
	FILE* fin=fopen(in_file,"r");
	FILE* fout=fopen(out_file,"w");
	fscanf(fin,"%d%d",&n,&p);
	//ai.resize(262145);
	int pow2= 1;
	for(int nn= n; nn; ++pow2, nn>>= 1);
	ai.resize((1 << pow2) + 1);
	build(1, 1, n);
	FORN(q,p)
	{
		int op;
		//debug(1, 1, n);
		fscanf(fin,"%d",&op);
		if (op == 3)
		{
			fprintf(fout, "%d\n", ai[1].len);
		}
		else
		{
			int x, y;
			fscanf(fin, "%d%d", &x, &y);
			update(1, 1, n, x, x + y - 1, op);
		}
	}
	fclose(fin);
	fclose(fout);
	
	return 0;
}