# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
968551 |
2024-04-23T15:20:26 Z |
njoop |
Trading (IZhO13_trading) |
C++14 |
|
146 ms |
17692 KB |
#include <bits/stdc++.h>
using namespace std;
struct trader {
int l, r, val;
};
struct cmp1 {
bool operator()(const trader &a, const trader &b) {
return a.r < b.r;
}
};
struct cmp2 {
bool operator()(const trader &a, const trader &b) {
return a.val < b.val;
}
};
int n, m, il, ir, ival, ans[300010];
priority_queue<trader, vector<trader>, cmp1> store;
priority_queue<trader, vector<trader>, cmp2> pq;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> il >> ir >> ival;
store.push({il, ir, ival+n-il});
}
for(int i=n; i>0; i--) {
while(store.size() && i <= store.top().r) {
pq.push(store.top());
store.pop();
}
while(pq.size() && pq.top().l > i) pq.pop();
if(pq.empty()) continue;
ans[i] = pq.top().val - (n-i);
}
for(int i=1; i<=n; i++) {
cout << ans[i] << " ";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
464 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
70 ms |
8732 KB |
Output is correct |
8 |
Correct |
76 ms |
8756 KB |
Output is correct |
9 |
Correct |
79 ms |
10944 KB |
Output is correct |
10 |
Correct |
88 ms |
11880 KB |
Output is correct |
11 |
Correct |
88 ms |
9784 KB |
Output is correct |
12 |
Correct |
104 ms |
12988 KB |
Output is correct |
13 |
Correct |
104 ms |
11828 KB |
Output is correct |
14 |
Correct |
113 ms |
12080 KB |
Output is correct |
15 |
Correct |
117 ms |
12888 KB |
Output is correct |
16 |
Correct |
129 ms |
13636 KB |
Output is correct |
17 |
Correct |
133 ms |
14780 KB |
Output is correct |
18 |
Correct |
126 ms |
16208 KB |
Output is correct |
19 |
Correct |
146 ms |
13840 KB |
Output is correct |
20 |
Correct |
143 ms |
17692 KB |
Output is correct |