Submission #340521

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340521	2020-12-27T19:53:21 Z	rqi	Trading (IZhO13_trading)	C++14	100 / 100	495 ms	23916 KB

trading

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define lb lower_bound

#define sz(x) (int)(x).size()

const int MOD = 1e9+7;

const int mx = 300005;
int N, M;
vpi trade[mx];

int curpos = 0;
set<pi> cur;

pi FIRST(){
	assert(sz(cur));
	return *(cur.begin());
}

void inc(){
	curpos++;
	while(sz(cur)){
		if(FIRST().s >= curpos) break;
		cur.erase(cur.begin());
	}
}

void INS(pi a){
	//look for first thing at most its value
	a.f = -a.f;
	auto it = cur.lb(mp(a.f, MOD));
	if(it != cur.begin() && (prev(it))->s >= a.s){
		return;
	}
	cur.insert(a);
	it = cur.find(a);
	while(true){
		if(next(it) == cur.end()) break;
		auto nit = next(it);
		if(nit->s <= a.s){
			cur.erase(nit);
		}
		else break;
	}
}

int query(){
	if(sz(cur) == 0) return 0;
	return -FIRST().f+curpos;
}

int main(){
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int L, R, X;
		cin >> L >> R >> X;
		trade[L].pb(mp(X-L, R));
	}

	for(int i = 1; i <= N; i++){
		inc();
		for(auto u: trade[i]){
			INS(u);
			//cout << "u: " << u.f << ", " << u.s << "\n";
		}
		cout << query() << " ";

		// cout << "cur: " << "\n";
		// for(auto u: cur){
		// 	cout << -u.f << " " << u.s << "\n";
		// }
		// cout << "\n";

	}
	cout << "\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7404 KB	Output is correct
2	Correct	5 ms	7404 KB	Output is correct
3	Correct	6 ms	7404 KB	Output is correct
4	Correct	6 ms	7404 KB	Output is correct
5	Correct	7 ms	7404 KB	Output is correct
6	Correct	8 ms	7532 KB	Output is correct
7	Correct	236 ms	15716 KB	Output is correct
8	Correct	259 ms	16736 KB	Output is correct
9	Correct	251 ms	16864 KB	Output is correct
10	Correct	274 ms	16500 KB	Output is correct
11	Correct	312 ms	18280 KB	Output is correct
12	Correct	302 ms	18268 KB	Output is correct
13	Correct	335 ms	18524 KB	Output is correct
14	Correct	316 ms	18648 KB	Output is correct
15	Correct	380 ms	20452 KB	Output is correct
16	Correct	416 ms	20708 KB	Output is correct
17	Correct	391 ms	20964 KB	Output is correct
18	Correct	397 ms	21736 KB	Output is correct
19	Correct	378 ms	20580 KB	Output is correct
20	Correct	495 ms	23916 KB	Output is correct