제출 #340521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340521		rqi	거래 (IZhO13_trading)	C++14	100 / 100	495 ms	23916 KiB

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