Submission #5401

#	Time	Username	Problem	Language	Result	Execution time	Memory
5401		Qwaz	Trading (IZhO13_trading)	C++98	100 / 100	344 ms	14576 KiB

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