Submission #426689

#TimeUsernameProblemLanguageResultExecution timeMemory
426689snasibov05RMQ (NOI17_rmq)C++14
0 / 100
1 ms204 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define oo 1000000000 struct range{ int l, r; int val; bool operator<(range r1) const{ return val < r1.val; } }; int main() { int n, q; cin >> n >> q; vector<range> v(q); for (int i = 0; i < q; ++i) { cin >> v[i].l >> v[i].r >> v[i].val; } sort(v.begin(), v.end()); vector<int> ans(n, oo); vector<int> cnt(n); int k = 0; bool flag = true; for (int i = 0; i < n; ++i){ int l = 0, r = n-1; while (k < q && v[k].val == i){ l = max(l, v[k].l); r = min(r, v[k].r); k++; } if (l > r) flag = false; for (int j = l; j <= r; ++j){ if (ans[j] > i) { ans[j] = i; cnt[i]++; } } if (cnt[i] == 0){ for (int j = l; j <= r; ++j){ if (cnt[ans[j]] > 1){ cnt[ans[j]]--; ans[j] = i; cnt[i]++; } } } if (cnt[i] == 0) flag = false; } if (flag){ for (int i = 0; i < n; ++i) { cout << ans[i] << " "; } } else{ for (int i = 0; i < n; ++i) { cout << "-1 "; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...