# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
20249 | 2016-08-02T15:19:44 Z | petil | Trading (IZhO13_trading) | C++14 | 501 ms | 64 KB |
#include <cstdio> #include <set> #include <vector> using namespace std; int n, m; struct info{ int x, L, idx; info(int a, int b, int c) : x(a), L(b), idx(c){} bool operator<(const info &i)const{ if (x == i.x){ if (idx == i.idx)return L < i.L; return idx < i.idx; } return x > i.x; } }; multiset < info > s; vector<info> st[300003], ed[300003]; int ans[300003]; int main(){ scanf("%d %d", &n, &m); for (int le, ri, x, i = 1; i <= m; i++){ scanf("%d %d %d", &le, &ri, &x); st[le].push_back(info(x-le, le, i)); ed[ri].push_back(info(x-le, le, i)); } for (int day = 1; day <= n; day++){ for (int i = 0; i < st[day].size(); i++) s.insert(info(st[day][i].x, st[day][i].L, st[day][i].idx)); if (s.empty())ans[day] = 0; else{ ans[day] = s.begin()->x + day; } for (int i = 0; i < ed[day].size(); i++){ auto it = s.find(ed[day][i]); s.erase(it); } } for (int i = 1; i <= n; i++)printf("%d ", ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 14 KB | Output is correct |
2 | Correct | 12 ms | 14 KB | Output is correct |
3 | Correct | 12 ms | 14 KB | Output is correct |
4 | Correct | 14 ms | 14 KB | Output is correct |
5 | Correct | 13 ms | 14 KB | Output is correct |
6 | Correct | 15 ms | 14 KB | Output is correct |
7 | Correct | 263 ms | 27 KB | Output is correct |
8 | Correct | 240 ms | 31 KB | Output is correct |
9 | Correct | 255 ms | 36 KB | Output is correct |
10 | Correct | 325 ms | 41 KB | Output is correct |
11 | Correct | 273 ms | 44 KB | Output is correct |
12 | Correct | 339 ms | 52 KB | Output is correct |
13 | Correct | 328 ms | 54 KB | Output is correct |
14 | Correct | 342 ms | 60 KB | Output is correct |
15 | Correct | 395 ms | 64 KB | Output is correct |
16 | Correct | 416 ms | 64 KB | Output is correct |
17 | Correct | 398 ms | 64 KB | Output is correct |
18 | Correct | 439 ms | 64 KB | Output is correct |
19 | Correct | 389 ms | 64 KB | Output is correct |
20 | Correct | 501 ms | 64 KB | Output is correct |