Submission #5401

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5401	2014-04-30T10:44:32 Z	Qwaz	Trading (IZhO13_trading)	C++	100 / 100	344 ms	14576 KB

trading

#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;
const int MAX = 300020;

struct events {
	int pos, h;
	bool open;

	events() {}
	events(int pos, int h, bool open) : pos(pos), h(h), open(open) {}

	bool operator < (const events &t) const {
		return pos < t.pos;
	}
};

int n, m, eFull;
events eList[MAX<<1];

void input(){
	scanf("%d%d", &n, &m);

	int i;
	for(i = 0; i<m; i++){
		int l, r, p;
		scanf("%d%d%d", &l, &r, &p);

		eList[eFull++] = events(l, p-l, 1);
		eList[eFull++] = events(r+1, p-l, 0);
	}

	sort(eList, eList+eFull);
}

multiset < int > st;

void solve(){
	int i, j = 0;
	for(i = 1; i<=n; i++){
		while(j < eFull && eList[j].pos == i){
			if(eList[j].open) st.insert(eList[j].h);
			else st.erase(st.lower_bound(eList[j].h));

			j++;
		}

		if(st.size() == 0) printf("0 ");
		else {
			multiset < int >::iterator it = st.end();
			it--;
			printf("%d ", *it+i);
		}
	}
	puts("");
}

int main(){
	input();

	solve();

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	8240 KB	Output is correct
2	Correct	0 ms	8240 KB	Output is correct
3	Correct	0 ms	8240 KB	Output is correct
4	Correct	0 ms	8240 KB	Output is correct
5	Correct	0 ms	8240 KB	Output is correct
6	Correct	0 ms	8240 KB	Output is correct
7	Correct	172 ms	10616 KB	Output is correct
8	Correct	180 ms	10352 KB	Output is correct
9	Correct	192 ms	11408 KB	Output is correct
10	Correct	232 ms	13124 KB	Output is correct
11	Correct	216 ms	10352 KB	Output is correct
12	Correct	268 ms	13520 KB	Output is correct
13	Correct	224 ms	11012 KB	Output is correct
14	Correct	260 ms	12728 KB	Output is correct
15	Correct	284 ms	12332 KB	Output is correct
16	Correct	308 ms	11276 KB	Output is correct
17	Correct	292 ms	12464 KB	Output is correct
18	Correct	332 ms	14576 KB	Output is correct
19	Correct	328 ms	12332 KB	Output is correct
20	Correct	344 ms	12200 KB	Output is correct