# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
757720 | 2023-06-13T15:55:59 Z | mdub | Stone Arranging 2 (JOI23_ho_t1) | C++14 | 96 ms | 22956 KB |
#include <bits/stdc++.h> using namespace std; int main () { int n; cin >> n; vector<int> a(n); set<int> s; for (int i = 0; i < n; i++) { cin >> a[i]; s.insert(a[i]); } map<int, int> compression; vector<int> revertedCompression(n + 1); auto it = s.begin(); for (int i = 1; i <= s.size(); i++) { compression[*it] = i; revertedCompression[i] = *it; it++; } for (int i = 0; i < n; i++) { a[i] = compression[a[i]]; } vector<pair<int, int>> bornes(n, {0, -1}); vector<set<int>> js(n + 1); for (int i = 0; i < n; i++) { //cout << a[i] << endl; if (js[a[i]].size()) { auto it = js[a[i]].end(); it--; int ind = *it; if (ind != i-1) { while (ind < i) { if (bornes[ind].first > 0) { ind = bornes[ind].second; js[-bornes[ind].first].erase(bornes[ind].second); } else { js[a[ind]].erase(ind); } ind++; } bornes[*it].first = a[i]; bornes[*it].second = i; bornes[i].first = -a[i]; bornes[i].second = i; } } js[a[i]].insert(i); } int cur = -1; for (int i = 0; i < bornes.size(); i++) { pair<int, int> elem = bornes[i]; if (elem.first > 0 && cur == -1) { cur = elem.first; } if (cur == -1) { cout << revertedCompression[a[i]] << '\n'; } else cout << revertedCompression[cur] << '\n'; if (elem.first == -cur) cur = -1; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 296 KB | Output is correct |
2 | Correct | 0 ms | 296 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 300 KB | Output is correct |
8 | Correct | 1 ms | 304 KB | Output is correct |
9 | Correct | 1 ms | 292 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 468 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 432 KB | Output is correct |
16 | Correct | 1 ms | 432 KB | Output is correct |
17 | Correct | 3 ms | 724 KB | Output is correct |
18 | Correct | 3 ms | 700 KB | Output is correct |
19 | Correct | 2 ms | 468 KB | Output is correct |
20 | Correct | 2 ms | 468 KB | Output is correct |
21 | Correct | 2 ms | 440 KB | Output is correct |
22 | Correct | 2 ms | 468 KB | Output is correct |
23 | Runtime error | 2 ms | 596 KB | Execution killed with signal 11 |
24 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 296 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 2 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 2 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 2 ms | 340 KB | Output is correct |
13 | Correct | 2 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 424 KB | Output is correct |
16 | Correct | 2 ms | 468 KB | Output is correct |
17 | Correct | 96 ms | 22908 KB | Output is correct |
18 | Correct | 93 ms | 22956 KB | Output is correct |
19 | Correct | 79 ms | 15808 KB | Output is correct |
20 | Correct | 81 ms | 15892 KB | Output is correct |
21 | Correct | 84 ms | 15892 KB | Output is correct |
22 | Correct | 78 ms | 15932 KB | Output is correct |
23 | Correct | 82 ms | 15864 KB | Output is correct |
24 | Correct | 83 ms | 15928 KB | Output is correct |
25 | Correct | 82 ms | 15932 KB | Output is correct |
26 | Correct | 76 ms | 16048 KB | Output is correct |
27 | Correct | 78 ms | 15860 KB | Output is correct |
28 | Correct | 81 ms | 15916 KB | Output is correct |
29 | Correct | 71 ms | 13516 KB | Output is correct |
30 | Correct | 94 ms | 22772 KB | Output is correct |
31 | Correct | 87 ms | 22932 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 296 KB | Output is correct |
2 | Correct | 0 ms | 296 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 300 KB | Output is correct |
8 | Correct | 1 ms | 304 KB | Output is correct |
9 | Correct | 1 ms | 292 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 468 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 432 KB | Output is correct |
16 | Correct | 1 ms | 432 KB | Output is correct |
17 | Correct | 3 ms | 724 KB | Output is correct |
18 | Correct | 3 ms | 700 KB | Output is correct |
19 | Correct | 2 ms | 468 KB | Output is correct |
20 | Correct | 2 ms | 468 KB | Output is correct |
21 | Correct | 2 ms | 440 KB | Output is correct |
22 | Correct | 2 ms | 468 KB | Output is correct |
23 | Runtime error | 2 ms | 596 KB | Execution killed with signal 11 |
24 | Halted | 0 ms | 0 KB | - |