제출 #13152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13152		woqja125	거래 (IZhO13_trading)	C++98	100 / 100	308 ms	16344 KiB

trading

#include<stdio.h>
#include<algorithm>
struct sales
{
	int l, r, x;
	bool operator<(const sales &A) const {return x<A.x;}
} dat[300001];
struct node
{
	node *l, *r;
	int x;
	node(){l=r=NULL; x=0;}
	void addRange(int s, int e, int f, int r, int x);
	int getx(int s, int e, int l);
};
int main()
{
	int n, m;
	int i;
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; i++)
	{
		scanf("%d%d%d", &dat[i].l, &dat[i].r, &dat[i].x);
		dat[i].x -= dat[i].l;
	}
	std::sort(dat+1, dat+1+m);
	node *ST = new node();
	for(i=1; i<=m; i++)
	{
		ST->addRange(1, n, dat[i].l, dat[i].r, i);
	}
	for(i=1; i<=n; i++)
	{
		int t = ST->getx(1, n, i);
		if(t==0) printf("0 ");
		else printf("%d ", dat[t].x + i);
	}
	return 0;
}


void node::addRange(int s, int e, int f, int r, int x)
{
	if(e < f || s > r) return;
	if(f <= s && e <= r)
	{
		this->x = x;
		return;
	}
	if(this->l == NULL)
	{
		this->l = new node();
		this->r = new node();
	}
	if(this->x != 0)
	{
		this->l->x = this->r->x = this->x;
		this->x = 0;
	}
	this->l->addRange(s, (s+e)/2, f, r, x);
	this->r->addRange((s+e)/2+1, e, f, r, x);
}

int node::getx(int s, int e, int l)
{
	if(this->x != 0) return x;
	if(this->l == NULL) return 0;
	if(l <= (s+e)/2) return this->l->getx(s, (s+e)/2, l);
	else return this->r->getx((s+e)/2+1, e, l);
}

• Subtask 1: 100 / 100