oj.uz

Submission #895928

# Submission time Handle Problem Language Result Execution time Memory
895928 2023-12-31T06:05:07 Z frostray8653 Stone Arranging 2 (JOI23_ho_t1) C++17
100 / 100
 147 ms 143396 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
#define IO ios::sync_with_stdio(0), cin.tie(0)
#define FOR(p, a, b) for (int p = a; p <= b; p++)
void dbg() {;}
template<class T, class ...U>
void dbg(T a, U ...b) {cout << a << (sizeof...(b) ? ", " : " "); dbg(b...);}
void ent() {cout << "\n";}
/// ---- INITIAL END ----

const int N = 200005;
int a[N];
vector<int> id;
deque<int> pos[N];
int get_id(int x) {
    return lower_bound(id.begin(), id.end(), x) - id.begin();
}

signed main() {
    IO;
    int n;
    cin >> n;
    FOR (i, 1, n) {
        cin >> a[i];
        id.push_back(a[i]);
    }
    sort(id.begin(), id.end());
    id.resize(unique(id.begin(), id.end()) - id.begin());
    
    deque<pii> dq;
    FOR (i, 1, n) {
        int x = get_id(a[i]);
        if (! pos[x].empty()) {
            int lst = pos[x].back();
            while (! dq.empty() && dq.back().first > lst) {
                pos[dq.back().second].pop_back();
                dq.pop_back();
            }
        } else {
            pos[x].push_back(i);
            dq.push_back({i, x});
        }
    }
    int now = 1, now_col = -1;
    for (pii p : dq) {
        for (; now < p.first; now++)
            cout << now_col << "\n";
        now_col = id[p.second];
    }
    for (; now <= n; now++)
        cout << id[dq.back().second] << "\n";

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 136004 KB Output is correct
2 Correct 59 ms 135760 KB Output is correct
3 Correct 60 ms 135804 KB Output is correct
4 Correct 59 ms 135772 KB Output is correct
5 Correct 63 ms 135764 KB Output is correct
6 Correct 67 ms 136044 KB Output is correct
7 Correct 63 ms 136008 KB Output is correct
8 Correct 59 ms 135764 KB Output is correct
9 Correct 62 ms 135936 KB Output is correct
10 Correct 65 ms 136052 KB Output is correct
11 Correct 69 ms 136016 KB Output is correct
12 Correct 65 ms 136020 KB Output is correct
13 Correct 67 ms 135956 KB Output is correct
14 Correct 68 ms 136048 KB Output is correct
15 Correct 69 ms 136020 KB Output is correct
16 Correct 66 ms 136052 KB Output is correct
17 Correct 65 ms 136028 KB Output is correct
18 Correct 66 ms 136024 KB Output is correct
19 Correct 66 ms 135916 KB Output is correct
20 Correct 69 ms 136060 KB Output is correct
21 Correct 68 ms 136024 KB Output is correct
22 Correct 69 ms 136020 KB Output is correct
23 Correct 68 ms 136020 KB Output is correct
24 Correct 66 ms 135820 KB Output is correct
25 Correct 66 ms 136020 KB Output is correct
26 Correct 67 ms 136052 KB Output is correct
27 Correct 77 ms 136048 KB Output is correct
28 Correct 66 ms 135976 KB Output is correct
29 Correct 61 ms 135836 KB Output is correct
30 Correct 62 ms 136016 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 136012 KB Output is correct
2 Correct 62 ms 135764 KB Output is correct
3 Correct 61 ms 136008 KB Output is correct
4 Correct 63 ms 135764 KB Output is correct
5 Correct 65 ms 135988 KB Output is correct
6 Correct 59 ms 135940 KB Output is correct
7 Correct 60 ms 135764 KB Output is correct
8 Correct 62 ms 136016 KB Output is correct
9 Correct 66 ms 136020 KB Output is correct
10 Correct 66 ms 136000 KB Output is correct
11 Correct 68 ms 136052 KB Output is correct
12 Correct 67 ms 136016 KB Output is correct
13 Correct 79 ms 135872 KB Output is correct
14 Correct 67 ms 136016 KB Output is correct
15 Correct 66 ms 136000 KB Output is correct
16 Correct 66 ms 136020 KB Output is correct
17 Correct 83 ms 138652 KB Output is correct
18 Correct 83 ms 138692 KB Output is correct
19 Correct 93 ms 138504 KB Output is correct
20 Correct 84 ms 138612 KB Output is correct
21 Correct 85 ms 138692 KB Output is correct
22 Correct 86 ms 138636 KB Output is correct
23 Correct 85 ms 138688 KB Output is correct
24 Correct 83 ms 138688 KB Output is correct
25 Correct 87 ms 138708 KB Output is correct
26 Correct 85 ms 138692 KB Output is correct
27 Correct 84 ms 138540 KB Output is correct
28 Correct 87 ms 138740 KB Output is correct
29 Correct 84 ms 138688 KB Output is correct
30 Correct 93 ms 138720 KB Output is correct
31 Correct 84 ms 138624 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 136004 KB Output is correct
2 Correct 59 ms 135760 KB Output is correct
3 Correct 60 ms 135804 KB Output is correct
4 Correct 59 ms 135772 KB Output is correct
5 Correct 63 ms 135764 KB Output is correct
6 Correct 67 ms 136044 KB Output is correct
7 Correct 63 ms 136008 KB Output is correct
8 Correct 59 ms 135764 KB Output is correct
9 Correct 62 ms 135936 KB Output is correct
10 Correct 65 ms 136052 KB Output is correct
11 Correct 69 ms 136016 KB Output is correct
12 Correct 65 ms 136020 KB Output is correct
13 Correct 67 ms 135956 KB Output is correct
14 Correct 68 ms 136048 KB Output is correct
15 Correct 69 ms 136020 KB Output is correct
16 Correct 66 ms 136052 KB Output is correct
17 Correct 65 ms 136028 KB Output is correct
18 Correct 66 ms 136024 KB Output is correct
19 Correct 66 ms 135916 KB Output is correct
20 Correct 69 ms 136060 KB Output is correct
21 Correct 68 ms 136024 KB Output is correct
22 Correct 69 ms 136020 KB Output is correct
23 Correct 68 ms 136020 KB Output is correct
24 Correct 66 ms 135820 KB Output is correct
25 Correct 66 ms 136020 KB Output is correct
26 Correct 67 ms 136052 KB Output is correct
27 Correct 77 ms 136048 KB Output is correct
28 Correct 66 ms 135976 KB Output is correct
29 Correct 61 ms 135836 KB Output is correct
30 Correct 62 ms 136016 KB Output is correct
31 Correct 59 ms 136012 KB Output is correct
32 Correct 62 ms 135764 KB Output is correct
33 Correct 61 ms 136008 KB Output is correct
34 Correct 63 ms 135764 KB Output is correct
35 Correct 65 ms 135988 KB Output is correct
36 Correct 59 ms 135940 KB Output is correct
37 Correct 60 ms 135764 KB Output is correct
38 Correct 62 ms 136016 KB Output is correct
39 Correct 66 ms 136020 KB Output is correct
40 Correct 66 ms 136000 KB Output is correct
41 Correct 68 ms 136052 KB Output is correct
42 Correct 67 ms 136016 KB Output is correct
43 Correct 79 ms 135872 KB Output is correct
44 Correct 67 ms 136016 KB Output is correct
45 Correct 66 ms 136000 KB Output is correct
46 Correct 66 ms 136020 KB Output is correct
47 Correct 83 ms 138652 KB Output is correct
48 Correct 83 ms 138692 KB Output is correct
49 Correct 93 ms 138504 KB Output is correct
50 Correct 84 ms 138612 KB Output is correct
51 Correct 85 ms 138692 KB Output is correct
52 Correct 86 ms 138636 KB Output is correct
53 Correct 85 ms 138688 KB Output is correct
54 Correct 83 ms 138688 KB Output is correct
55 Correct 87 ms 138708 KB Output is correct
56 Correct 85 ms 138692 KB Output is correct
57 Correct 84 ms 138540 KB Output is correct
58 Correct 87 ms 138740 KB Output is correct
59 Correct 84 ms 138688 KB Output is correct
60 Correct 93 ms 138720 KB Output is correct
61 Correct 84 ms 138624 KB Output is correct
62 Correct 96 ms 140532 KB Output is correct
63 Correct 142 ms 141420 KB Output is correct
64 Correct 143 ms 141016 KB Output is correct
65 Correct 98 ms 139968 KB Output is correct
66 Correct 90 ms 139972 KB Output is correct
67 Correct 92 ms 140264 KB Output is correct
68 Correct 93 ms 140212 KB Output is correct
69 Correct 96 ms 140360 KB Output is correct
70 Correct 97 ms 140220 KB Output is correct
71 Correct 93 ms 140268 KB Output is correct
72 Correct 95 ms 140228 KB Output is correct
73 Correct 130 ms 141744 KB Output is correct
74 Correct 140 ms 141760 KB Output is correct
75 Correct 147 ms 143396 KB Output is correct
76 Correct 147 ms 143308 KB Output is correct
77 Correct 143 ms 143292 KB Output is correct
78 Correct 142 ms 143292 KB Output is correct