oj.uz

Submission #4778

# Submission time Handle Problem Language Result Execution time Memory
4778 2014-01-01T10:45:21 Z tncks0121 Trading (IZhO13_trading) C++
100 / 100
 224 ms 10508 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5896 KB Output is correct
2 Correct 0 ms 5896 KB Output is correct
3 Correct 0 ms 5896 KB Output is correct
4 Correct 0 ms 5896 KB Output is correct
5 Correct 0 ms 5896 KB Output is correct
6 Correct 4 ms 5896 KB Output is correct
7 Correct 124 ms 7052 KB Output is correct
8 Correct 124 ms 7052 KB Output is correct
9 Correct 136 ms 8204 KB Output is correct
10 Correct 144 ms 10508 KB Output is correct
11 Correct 152 ms 8204 KB Output is correct
12 Correct 164 ms 10508 KB Output is correct
13 Correct 176 ms 8204 KB Output is correct
14 Correct 176 ms 8204 KB Output is correct
15 Correct 196 ms 10508 KB Output is correct
16 Correct 180 ms 8204 KB Output is correct
17 Correct 200 ms 8204 KB Output is correct
18 Correct 216 ms 10508 KB Output is correct
19 Correct 220 ms 10508 KB Output is correct
20 Correct 224 ms 8204 KB Output is correct