Submission #1224070

#TimeUsernameProblemLanguageResultExecution timeMemory
1224070lopkusRMQ (NOI17_rmq)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> l(q), r(q), x(q); for(int i = 0; i < q; i++) { std::cin >> l[i] >> r[i] >> x[i]; } std::vector<int> b(n); for(int i = 0; i < q; i++) { for(int j = l[i]; j <= r[i]; j++) { b[j] = std::max(b[j], x[i]); } } std::vector<int> pos(n, - 1); for(int i = 0; i < n; i++) { if(pos[b[i]] == - 1) { pos[b[i]] = i; } } std::vector<int> a(n, - 1); for(int i = 0; i < n; i++) { if(pos[i] != - 1) { a[pos[i]] = i; } } std::vector<std::pair<int, int>> ops; for(int i = 0; i < n; i++) { if(a[i] != - 1) { continue; } ops.push_back({b[i], i}); } std::sort(ops.begin(), ops.end()); std::reverse(ops.begin(), ops.end()); int curr = n - 1; for(int i = 0; i < ops.size(); i++) { a[ops[i].second] = curr--; } int can = 1; std::vector<int> was(n); for(int i = 0; i < n; i++) { if(was[a[i]]) { can = 0; } was[a[i]] = 1; } for(int i = 0; i < q; i++) { int mn = n; for(int j = l[i]; j <= r[i]; j++) { mn = std::min(mn, a[j]); } if(mn != x[i]) { can = 0; } } if(!can) { for(int i = 0; i < n; i++) { a[i] = - 1; } } for(int i = 0; i < n; i++) { std::cout << a[i] << " "[i == n - 1]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...