| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 674953 |
2022-12-26T16:54:12 Z |
QwertyPi |
RMQ (NOI17_rmq) |
C++14 |
|
4 ms |
5716 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5 + 11;
struct SegTree{
int t[MAXN << 2];
void init() {
fill(t, t + (MAXN << 2), (1 << 30));
}
void upd(int ql, int qr, int val, int v, int l, int r){
if(qr < l || r < ql) return;
if(ql <= l && r <= qr){
t[v] = max(t[v], val);
return;
}
t[v * 2 + 1] = max(t[v], t[v * 2 + 1]);
t[v * 2 + 2] = max(t[v], t[v * 2 + 2]);
int m = (l + r) / 2;
upd(ql, qr, val, v * 2 + 1, l, m);
upd(ql, qr, val, v * 2 + 2, m + 1, r);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
int qry(int ql, int qr, int v, int l, int r){
if(qr < l || r < ql) return (1 << 30);
if(ql <= l && r <= qr) return t[v];
t[v * 2 + 1] = max(t[v], t[v * 2 + 1]);
t[v * 2 + 2] = max(t[v], t[v * 2 + 2]);
int m = (l + r) / 2;
return min(qry(ql, qr, v * 2 + 1, l, m), qry(ql, qr, v * 2 + 2, m + 1, r));
}
} segTree, segTree2;
struct con{
int l, r, m;
};
vector<con> Q[MAXN];
int ans[MAXN];
bool used[MAXN], used2[MAXN];
int l[MAXN], r[MAXN];
int main(){
segTree.init(); segTree2.init();
int n, q; cin >> n >> q;
vector<con> cons;
for(int i = 0; i < q; i++){
int l, r, m; cin >> l >> r >> m;
cons.push_back({l, r, m});
Q[m].push_back({l, r, m});
segTree.upd(l, r, m, 0, 0, n - 1);
}
auto die = [&n](){
for(int i = 0; i < n; i++){
cout << -1 << ' ';
}
cout << endl;
exit(0);
};
for(int i = 0; i < q; i++){
int q = segTree.qry(cons[i].l, cons[i].r, 0, 0, n - 1);
if(q > cons[i].m) die();
}
vector<con> cons2;
for(int i = 0; i < n; i++){
int l = 0, r = n - 1;
for(auto c : Q[i]){
l = max(l, c.l), r = min(r, c.r);
}
if(l > r) die();
}
for(int i = 0; i < n; i++){
l[i] = (1 << 30), r[i] = -(1 << 30);
}
for(int i = 0; i < n; i++){
int v = segTree.qry(i, i, 0, 0, n - 1);
if(v == (1 << 30)) continue;
l[v] = min(l[v], i), r[v] = max(r[v], i);
}
for(int i = 0; i < n; i++){
if(l[i] != (1 << 30)){
cons2.push_back({l[i], r[i], i});
}
}
sort(cons2.begin(), cons2.end(), [](con a, con b){
return a.r - a.l < b.r - b.l;
});
auto give = [](int idx, int val){
used[idx] = true, used2[val] = true;
ans[idx] = val;
};
for(auto i : cons2){
for(int j = i.l; j <= i.r; j++){
if(!used[j]) {
give(j, i.m);
break;
}
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 0; i < n; i++) if(!used[i]) pq.push({segTree.qry(i, i, 0, 0, n - 1), i});
for(int i = 0; i < n; i++) if(!used2[i]) {
auto p = pq.top(); pq.pop();
ans[p.se] = i;
}
for(int i = 0; i < n; i++) segTree2.upd(i, i, ans[i], 0, 0, n - 1);
for(int i = 0; i < q; i++){
int q = segTree2.qry(cons[i].l, cons[i].r, 0, 0, n - 1);
if(q != cons[i].m) die();
}
for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
}
Compilation message
rmq.cpp: In function 'int main()':
rmq.cpp:124:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
124 | for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
| ^~~
rmq.cpp:124:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
124 | for(int i = 0; i < n; i++) cout << ans[i] << ' '; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
