| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 293171 |
2020-09-07T17:23:25 Z |
Berted |
RMQ (NOI17_rmq) |
C++14 |
|
193 ms |
9976 KB |
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<int, pii>
using namespace std;
ppi interval[100001];
vector<int> rollback[100001];
set<int> s;
int n, q, ans[100001];
bool ins[100001];
pii intersect(pii &a, pii &b)
{
return {max(a.fst, b.fst), min(a.snd, b.snd)};
}
int main()
{
bool fail = 0;
cin >> n >> q;
for (int i = 0; i < n; i++) {ans[i] = -1; s.insert(i);}
for (int i = 0; i < q; i++)
{
cin >> interval[i].snd.fst >> interval[i].snd.snd >> interval[i].fst;
}
sort(interval, interval + q, greater<ppi>());
int j = 0;
for (int i = n - 1; i >= 0; i--)
{
pii ivl = {0, n - 1};
for (int k = j; k < q && interval[k].fst == i; k++) {ivl = intersect(ivl, interval[k].snd);}
if (ivl != make_pair(0, n - 1))
{
auto it = s.lower_bound(ivl.fst);
if (it != s.end() && *it <= ivl.snd) {ans[*it] = i; s.erase(it); ins[i] = 1;}
else {fail = 1; break;}
}
for (; j < q && interval[j].fst == i; j++)
{
auto it = s.lower_bound(interval[j].snd.fst);
while (it != s.end() && *it <= interval[j].snd.snd)
{
rollback[i].push_back(*it);
it = s.erase(it);
}
}
}
for (int i = 0; i < n; i++)
{
for (auto &x : rollback[i]) {s.insert(x);}
if (!ins[i])
{
if (s.size()) {ans[*s.begin()] = i; s.erase(s.begin());}
else {fail = 1; break;}
}
}
if (fail)
{
for (int i = 0; i < n; i++) {ans[i] = -1;}
}
for (int i = 0; i < n; i++)
{
cout << ans[i];
if (i + 1 < n) cout << " ";
}
cout << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 13 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 15 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 17 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 22 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2816 KB |
Output is correct |
| 24 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 13 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 14 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 15 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 17 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 19 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 22 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2816 KB |
Output is correct |
| 24 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 26 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 27 |
Correct |
193 ms |
9340 KB |
Output is correct |
| 28 |
Correct |
166 ms |
9464 KB |
Output is correct |
| 29 |
Correct |
141 ms |
8952 KB |
Output is correct |
| 30 |
Correct |
180 ms |
9976 KB |
Output is correct |
| 31 |
Correct |
147 ms |
8440 KB |
Output is correct |
| 32 |
Correct |
181 ms |
8568 KB |
Output is correct |
| 33 |
Correct |
45 ms |
7672 KB |
Output is correct |
| 34 |
Correct |
31 ms |
6144 KB |
Output is correct |
| 35 |
Correct |
63 ms |
8568 KB |
Output is correct |
| 36 |
Correct |
125 ms |
9204 KB |
Output is correct |
| 37 |
Correct |
168 ms |
9592 KB |
Output is correct |
| 38 |
Correct |
25 ms |
6272 KB |
Output is correct |
| 39 |
Correct |
144 ms |
9208 KB |
Output is correct |
| 40 |
Correct |
2 ms |
2688 KB |
Output is correct |
| 41 |
Correct |
2 ms |
2688 KB |
Output is correct |
