제출 #5407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5407		gs12006	거래 (IZhO13_trading)	C++98	30 / 100	12 ms	2792 KiB

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[66000];

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

int c[33000];


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: 30 / 100