记录编号	81913	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]借教室	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	2.211 s
提交时间	2013-11-19 17:58:05	内存使用	0.30 MiB

#include <fstream>

using namespace std;

ifstream in("classrooms.in");
ofstream out("classrooms.out");

struct node
{
	long start;
	long end;
	long rooms;
};

long n,m;
long *rest;
node *order;
long *comp;

void input();
void proc();

int main()
{
	input();
	proc();
	return 0;
}

void input()
{
	in>>n>>m;
	rest=new long [n+1];
	comp=new long [n+2];
	order=new node [m+1];
	for(long i=1;i!=n+1;++i)
	{
		in>>rest[i];
	}
	for(long i=1;i!=m+1;++i)
	{
		register long s,e,r;
		in>>r>>s>>e;
		order[i].start=s;
		order[i].end=e;
		order[i].rooms=r;
	}
}

bool partition(long s, long e)
{
	long mi(s+(e-s)/2);
	for(int i=1;i!=n+1;++i)
	{
		comp[i]=0;
	}
	for(int i=1;i!=mi+1;++i)
	{
		comp[order[i].start]+=order[i].rooms;
		comp[order[i].end+1]-=order[i].rooms;
	}
	long temp(0);
	for(int i=1;i!=n+1;++i)
	{
		temp+=comp[i];
		if(rest[i]<temp)
		{
			return false;
		}
	}
	return true;
}

void proc()
{
	long start(1);
	long end(m);//m敲成n了
	if(partition(1, 2*m-3))
	{
		out<<0<<endl;
		return ;
	}
	while(end!=start)
	{
		bool btemp(partition(start, end));
		if(!btemp)
		{
			end=start+(end-start)/2;
		}
		else
		{
			start=end-(end-start)/2;
		}
	}
	out<<-1<<endl<<start<<endl;
}