Submission #1010546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010546		bornag	Trading (IZhO13_trading)	C++14	100 / 100	243 ms	28728 KiB

trading

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

#define ll long long

const int maxn = 300007;

ll n, m;
ll li, ri, xi;

ll values[maxn];

struct trader{
	ll l; ll r; ll x;
	
	trader(){}
	trader(ll _l, ll _r, ll _x){
		x = _x; l = _l; r = _r;
	}
	
	friend bool operator < (const trader &a, const trader &b){
		
		ll ai = a.x + b.l - a.l;
		ll bi = b.x;
		
		return ai < bi;
	}
};

vector<trader> salesmen[maxn];

int main(){
	cin >> n >> m;
	
	priority_queue<trader> q;
	for(int i = 0; i < m; i++){
		cin >> li >> ri >> xi;
		li--; ri--;
		
		//cout << li << ' ' << ri << ' ' << xi;
		salesmen[li].push_back(trader(li, ri, xi));
		//cout << salesmen[0][0].x << '\n';
	}
	
	
	
	for(int i = 0; i < n; i++){
		for(auto t : salesmen[i]){
			q.push(t);
			//cout << t.x << ' ' << i << '\n';
		}
		
		while(!q.empty() && q.top().r < i){
			q.pop();
		}
		
		if(!q.empty()) values[i] = q.top().x + i-q.top().l;
	}
	
	for(int i = 0; i < n; i++)
		cout << values[i] << ' ';
}

• Subtask 1: 100 / 100