oj.uz

Submission #13152

# Submission time Handle Problem Language Result Execution time Memory
13152 2015-02-01T08:34:43 Z woqja125 Trading (IZhO13_trading) C++
100 / 100
 308 ms 16344 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4728 KB Output is correct
2 Correct 0 ms 4728 KB Output is correct
3 Correct 0 ms 4728 KB Output is correct
4 Correct 0 ms 4728 KB Output is correct
5 Correct 0 ms 4728 KB Output is correct
6 Correct 2 ms 4860 KB Output is correct
7 Correct 145 ms 10404 KB Output is correct
8 Correct 184 ms 13440 KB Output is correct
9 Correct 177 ms 11592 KB Output is correct
10 Correct 179 ms 8556 KB Output is correct
11 Correct 204 ms 15288 KB Output is correct
12 Correct 187 ms 11724 KB Output is correct
13 Correct 210 ms 14232 KB Output is correct
14 Correct 248 ms 11592 KB Output is correct
15 Correct 247 ms 13968 KB Output is correct
16 Correct 244 ms 13704 KB Output is correct
17 Correct 226 ms 13308 KB Output is correct
18 Correct 260 ms 15816 KB Output is correct
19 Correct 308 ms 13440 KB Output is correct
20 Correct 286 ms 16344 KB Output is correct