Submission #5408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5408	2014-04-30T12:23:39 Z	gs12006	Trading (IZhO13_trading)	C++	100 / 100	380 ms	23080 KB

trading

#include <stdio.h>
#include<queue>
#include <algorithm>
using namespace std;

priority_queue< pair<int,pair<int,pair<int,pair<int,int> > > > > st;

struct mc
{
	int x,n,h,t,e;
}a[660000];

bool cmp(mc x,mc y)
{
	if (x.x==y.x) return x.t<y.t;
	else return x.x<y.x; 
}

int c[330000];


int main()
{
	int n,m,ts,te,th,i,rs=1,j;
	mc tmc;
	scanf("%d %d",&n,&m);
	for (i=0;i<m;i++)
	{
		scanf("%d %d %d",&ts,&te,&th);
		tmc.x=ts;
		tmc.n=i+1;
		tmc.h=th;
		tmc.t=0;
		tmc.e=te;
		a[2*i]=tmc;
		tmc.x=te;
		tmc.n=i+1;
		tmc.h=th;
		tmc.t=1;
		a[2*i+1]=tmc;
	}
	sort(a,a+2*m,cmp);
	for (i=0;i<2*m;i++)
	{
		if (a[i].t==0)
		{
			if (st.empty())
			{
				for (j=rs;j<a[i].x;j++) printf("0 ");
				rs=a[i].x;
			}
			else if (a[i].h>st.top().second.first+a[i].x-st.top().second.second.second.first)
			{
				for (j=st.top().second.first+rs-st.top().second.second.second.first;j<st.top().second.first+a[i].x-st.top().second.second.second.first;j++) printf("%d ",j);
				rs=a[i].x;
			}
			st.push(make_pair(a[i].h-a[i].x,make_pair(a[i].h,make_pair(a[i].n,make_pair(a[i].x,a[i].e)))));
		}
		else
		{
			c[a[i].n]++;
			if (st.top().second.second.first==a[i].n)
			{
				for (j=st.top().second.first+rs-st.top().second.second.second.first;j<=st.top().second.first+a[i].x-st.top().second.second.second.first;j++) printf("%d ",j);
				rs=a[i].x+1;
			}
			while (!st.empty()&&c[st.top().second.second.first]>0) st.pop();
		}
	}
	for (j=rs;j<=n;j++) printf("0 ");
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	15392 KB	Output is correct
2	Correct	0 ms	15392 KB	Output is correct
3	Correct	0 ms	15392 KB	Output is correct
4	Correct	0 ms	15392 KB	Output is correct
5	Correct	0 ms	15392 KB	Output is correct
6	Correct	0 ms	15552 KB	Output is correct
7	Correct	192 ms	17320 KB	Output is correct
8	Correct	216 ms	17320 KB	Output is correct
9	Correct	200 ms	19240 KB	Output is correct
10	Correct	236 ms	23080 KB	Output is correct
11	Correct	216 ms	19240 KB	Output is correct
12	Correct	260 ms	23080 KB	Output is correct
13	Correct	248 ms	19240 KB	Output is correct
14	Correct	280 ms	19240 KB	Output is correct
15	Correct	304 ms	23080 KB	Output is correct
16	Correct	336 ms	19240 KB	Output is correct
17	Correct	308 ms	19240 KB	Output is correct
18	Correct	340 ms	23080 KB	Output is correct
19	Correct	328 ms	23080 KB	Output is correct
20	Correct	380 ms	19240 KB	Output is correct