Submission #4778

#	Time	Username	Problem	Language	Result	Execution time	Memory
4778		tncks0121	Trading (IZhO13_trading)	C++98	100 / 100	224 ms	10508 KiB

trading

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;


struct merchant {
	int l, r, x;
	merchant (int l = 0, int r = 0, int x = 0): l(l), r(r), x(x) { }
	bool operator< (const merchant &m) const { return x < m.x; }
};

const int N_ = 300005;
const int M_ = 300005;

int N, M;
merchant D[M_];
bool cmpD (const merchant &a, const merchant &b) { return a.l < b.l; }

int Res[N_];

priority_queue<merchant> PQ;

int main() {
	int i, j, k;

	scanf("%d%d", &N, &M);
	for(i = 1; i <= M; i++) {
		int l, r, x; scanf("%d%d%d", &l, &r, &x);
		D[i] = merchant(l, r, x - l);
	}

	sort(D+1, D+M+1, cmpD);

	for(i = 1, k = 1; k <= N; k++) {
		while(i <= M && D[i].l == k) {
			PQ.push (D[i]);
			++i;
		}
		while(!PQ.empty() && PQ.top().r < k) PQ.pop();
		if(!PQ.empty()) Res[k] = PQ.top().x + k;
	}

	for(i = 1; i <= N; i++) {
		printf("%d ", Res[i]);
	}

	return 0;
}

• Subtask 1: 100 / 100