oj.uz

답안 #204180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204180 2020-02-24T21:35:23 Z DS007 Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 5521 ms 215636 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 1000;
map<int, int> m;
int t[N * 8], lazy[N * 8];
multiset<int> pos[N];

void push_down(int v) {
    t[v] += lazy[v];
    lazy[v * 2] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int l, int r, int tl, int tr, int val) {
    if (tl > tr)
        return;
    push_down(v); push_down(v * 2); push_down(v * 2 + 1);
    if (l == tl && r == tr) {
        lazy[v] += val;
        push_down(v);
        return;
    }

    int mid = (l + r) / 2;
    update(v * 2, l, mid, tl, min(mid, tr), val);
    update(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr, val);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}

void add(int e, int i) {
    update(1, 0, N - 1, e, N - 1, -1);
    int dif = pos[e].empty() ? 0 : *pos[e].rbegin();
    pos[e].insert(i);
    dif = *pos[e].rbegin() - dif;
    update(1, 0, N - 1, e, e, dif);
}

void remove(int e, int i) {
    update(1, 0, N - 1, e, N - 1, 1);
    int dif = *pos[e].rbegin();
    pos[e].erase(i);
    dif = pos[e].empty() ? -dif : *pos[e].rbegin() - dif;
    update(1, 0, N - 1, e, e, dif);
}

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    for (auto &i : pos) i.insert(0);
    for (auto &i : a) m[i] = 0;
    for (auto &i : v) m[i] = 0;
    int cur = 0;
    for (auto &i : m) i.second = cur++;

    for (int i = 0; i < a.size(); i++) {
        a[i] = m[a[i]];
        add(a[i], i + 1);
    }

    vector<int> ans;
    for (int i = 0; i < x.size(); i++) {
        v[i] = m[v[i]];
        remove(a[x[i]], x[i] + 1);
        add(v[i], x[i] + 1);
        a[x[i]] = v[i];
        ans.push_back(t[1]);
        // cout << t[1] << "\n";
    }

    return ans;
}

/*signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    countScans({1, 2, 3, 4}, {0, 2}, {3, 1});
}*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++) {
                     ~~^~~~~~~~~~
bubblesort2.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < x.size(); i++) {
                     ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 94584 KB Output is correct
2 Correct 102 ms 94712 KB Output is correct
3 Correct 108 ms 94968 KB Output is correct
4 Correct 103 ms 94968 KB Output is correct
5 Correct 116 ms 95096 KB Output is correct
6 Correct 104 ms 94968 KB Output is correct
7 Correct 108 ms 94968 KB Output is correct
8 Correct 110 ms 95188 KB Output is correct
9 Correct 110 ms 94968 KB Output is correct
10 Correct 103 ms 94968 KB Output is correct
11 Correct 107 ms 94968 KB Output is correct
12 Correct 106 ms 94968 KB Output is correct
13 Correct 104 ms 94968 KB Output is correct
14 Correct 105 ms 94968 KB Output is correct
15 Correct 103 ms 94968 KB Output is correct
16 Correct 108 ms 94912 KB Output is correct
17 Correct 110 ms 94968 KB Output is correct
18 Correct 103 ms 94968 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 94584 KB Output is correct
2 Correct 102 ms 94712 KB Output is correct
3 Correct 108 ms 94968 KB Output is correct
4 Correct 103 ms 94968 KB Output is correct
5 Correct 116 ms 95096 KB Output is correct
6 Correct 104 ms 94968 KB Output is correct
7 Correct 108 ms 94968 KB Output is correct
8 Correct 110 ms 95188 KB Output is correct
9 Correct 110 ms 94968 KB Output is correct
10 Correct 103 ms 94968 KB Output is correct
11 Correct 107 ms 94968 KB Output is correct
12 Correct 106 ms 94968 KB Output is correct
13 Correct 104 ms 94968 KB Output is correct
14 Correct 105 ms 94968 KB Output is correct
15 Correct 103 ms 94968 KB Output is correct
16 Correct 108 ms 94912 KB Output is correct
17 Correct 110 ms 94968 KB Output is correct
18 Correct 103 ms 94968 KB Output is correct
19 Correct 128 ms 96376 KB Output is correct
20 Correct 135 ms 96760 KB Output is correct
21 Correct 140 ms 96760 KB Output is correct
22 Correct 135 ms 96660 KB Output is correct
23 Correct 127 ms 96480 KB Output is correct
24 Correct 133 ms 96504 KB Output is correct
25 Correct 126 ms 96376 KB Output is correct
26 Correct 131 ms 96380 KB Output is correct
27 Correct 126 ms 96248 KB Output is correct
28 Correct 135 ms 96252 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 95992 KB Output is correct
2 Correct 207 ms 97340 KB Output is correct
3 Correct 299 ms 98424 KB Output is correct
4 Correct 299 ms 98552 KB Output is correct
5 Correct 282 ms 98424 KB Output is correct
6 Correct 278 ms 98424 KB Output is correct
7 Correct 286 ms 98424 KB Output is correct
8 Correct 287 ms 98424 KB Output is correct
9 Correct 286 ms 98588 KB Output is correct
10 Correct 263 ms 98424 KB Output is correct
11 Correct 276 ms 98724 KB Output is correct
12 Correct 260 ms 98424 KB Output is correct
13 Correct 262 ms 98424 KB Output is correct
14 Correct 275 ms 98424 KB Output is correct
15 Correct 264 ms 98424 KB Output is correct
16 Correct 258 ms 98424 KB Output is correct
17 Correct 257 ms 98392 KB Output is correct
18 Correct 251 ms 98424 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 94584 KB Output is correct
2 Correct 102 ms 94712 KB Output is correct
3 Correct 108 ms 94968 KB Output is correct
4 Correct 103 ms 94968 KB Output is correct
5 Correct 116 ms 95096 KB Output is correct
6 Correct 104 ms 94968 KB Output is correct
7 Correct 108 ms 94968 KB Output is correct
8 Correct 110 ms 95188 KB Output is correct
9 Correct 110 ms 94968 KB Output is correct
10 Correct 103 ms 94968 KB Output is correct
11 Correct 107 ms 94968 KB Output is correct
12 Correct 106 ms 94968 KB Output is correct
13 Correct 104 ms 94968 KB Output is correct
14 Correct 105 ms 94968 KB Output is correct
15 Correct 103 ms 94968 KB Output is correct
16 Correct 108 ms 94912 KB Output is correct
17 Correct 110 ms 94968 KB Output is correct
18 Correct 103 ms 94968 KB Output is correct
19 Correct 128 ms 96376 KB Output is correct
20 Correct 135 ms 96760 KB Output is correct
21 Correct 140 ms 96760 KB Output is correct
22 Correct 135 ms 96660 KB Output is correct
23 Correct 127 ms 96480 KB Output is correct
24 Correct 133 ms 96504 KB Output is correct
25 Correct 126 ms 96376 KB Output is correct
26 Correct 131 ms 96380 KB Output is correct
27 Correct 126 ms 96248 KB Output is correct
28 Correct 135 ms 96252 KB Output is correct
29 Correct 138 ms 95992 KB Output is correct
30 Correct 207 ms 97340 KB Output is correct
31 Correct 299 ms 98424 KB Output is correct
32 Correct 299 ms 98552 KB Output is correct
33 Correct 282 ms 98424 KB Output is correct
34 Correct 278 ms 98424 KB Output is correct
35 Correct 286 ms 98424 KB Output is correct
36 Correct 287 ms 98424 KB Output is correct
37 Correct 286 ms 98588 KB Output is correct
38 Correct 263 ms 98424 KB Output is correct
39 Correct 276 ms 98724 KB Output is correct
40 Correct 260 ms 98424 KB Output is correct
41 Correct 262 ms 98424 KB Output is correct
42 Correct 275 ms 98424 KB Output is correct
43 Correct 264 ms 98424 KB Output is correct
44 Correct 258 ms 98424 KB Output is correct
45 Correct 257 ms 98392 KB Output is correct
46 Correct 251 ms 98424 KB Output is correct
47 Correct 1501 ms 135212 KB Output is correct
48 Incorrect 5521 ms 215636 KB Output isn't correct
49 Halted 0 ms 0 KB -