oj.uz

Submission #1013729

# Submission time Handle Problem Language Result Execution time Memory
1013729 2024-07-04T04:29:44 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 33 ms 3480 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
// using ii = pair <ll, ll>;
// using vii = vector <ii>;

const ll MAXN = 1E4+16, INF = ll(1E18)+16;
priority_queue <ll> pq[MAXN];

struct Fenwick {
    vll tree;
    ll n;

    Fenwick (ll n): tree(n, 0), n(n) {}

    void update (ll id, ll val) {
        for (; id < n; id |= id+1) tree[id] += val;
    }

    ll query (ll id) {
        ll ans = 0;
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
};

struct SegTree {
    vll tree;
    ll n;

    SegTree (ll n): tree(2*n, 0), n(n) {}

    void update (ll id, ll val) {
        tree[id] = val;
    }

    void update (ll ql, ll qr, ll val) {
        for (ll i = ql; i <= qr; i++) tree[i] += val;
    }

    ll query (ll ql, ll qr) {
        ll ans = -INF;
        for (ll i = ql; i <= qr; i++) ans = max(ans, tree[i]);
        return ans;
    }
};

vi countScans (vi a, vi wh, vi val) {
    vll ve(a.begin(), a.end());
    ll n = a.size();
    ll Q = wh.size();
    {vll th = ve;
    for (int i : val) th.push_back(i);
    sort(th.begin(), th.end());
    th.resize(unique(th.begin(), th.end()) - th.begin());
    for (ll &i : ve) i = lower_bound(th.begin(), th.end(), i) - th.begin();
    for (int &i : val) i = lower_bound(th.begin(), th.end(), i) - th.begin();}
    Fenwick ftFreq(MAXN);
    SegTree stAns(MAXN);
    vi ans;
    for (ll i = 0; i < n; i++) {
        pq[ve[i]].push(i);
        ftFreq.update(ve[i], +1);
    }
    auto redo = [&](ll i) {
        while (pq[i].size() && ve[pq[i].top()] != i) pq[i].pop();
        stAns.update(i, -INF);
        if (!pq[i].size()) return;
        stAns.update(i, pq[i].top()+1 - ftFreq.query(i));
    };
    for (ll i = 0; i < n+wh.size(); i++) redo(i);
    // for (ll i = 0; i < n+wh.size(); i++) cerr << stAns.query(0, i) << ' ';
    // cerr << '\n';
    for (ll q = 0; q < Q; q++) {
        ll val1 = ve[wh[q]], val2 = val[q];
        ftFreq.update(ve[wh[q]], -1);
        ve[wh[q]] = val[q];
        ftFreq.update(ve[wh[q]], +1);
        pq[val[q]].push(wh[q]);
        stAns.update(val1, MAXN-4, +1);
        stAns.update(val2, MAXN-4, -1);
        redo(val1);
        redo(val2);
        // cerr << val1 << ' ' << val2 << '\n';
        // for (ll i : ve) cerr << i << ' '; cerr << '\n';
        // for (ll i = 0; i < n+wh.size(); i++) cerr << stAns.query(i, i) << ' ';
        // cerr << '\n';
        ans.push_back(stAns.query(0, MAXN-8));
    }
    return ans;
}

Compilation message

bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:74:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'long long unsigned int' [-Wsign-compare]
   74 |     for (ll i = 0; i < n+wh.size(); i++) redo(i);
      |                    ~~^~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 14 ms 1088 KB Output is correct
3 Correct 27 ms 1116 KB Output is correct
4 Correct 27 ms 1200 KB Output is correct
5 Correct 33 ms 1116 KB Output is correct
6 Correct 26 ms 1116 KB Output is correct
7 Correct 27 ms 1108 KB Output is correct
8 Correct 27 ms 1080 KB Output is correct
9 Correct 32 ms 1116 KB Output is correct
10 Correct 27 ms 1116 KB Output is correct
11 Correct 32 ms 1116 KB Output is correct
12 Correct 28 ms 1116 KB Output is correct
13 Correct 28 ms 1116 KB Output is correct
14 Correct 26 ms 1116 KB Output is correct
15 Correct 27 ms 1116 KB Output is correct
16 Correct 28 ms 1172 KB Output is correct
17 Correct 28 ms 1116 KB Output is correct
18 Correct 28 ms 1116 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 14 ms 1088 KB Output is correct
3 Correct 27 ms 1116 KB Output is correct
4 Correct 27 ms 1200 KB Output is correct
5 Correct 33 ms 1116 KB Output is correct
6 Correct 26 ms 1116 KB Output is correct
7 Correct 27 ms 1108 KB Output is correct
8 Correct 27 ms 1080 KB Output is correct
9 Correct 32 ms 1116 KB Output is correct
10 Correct 27 ms 1116 KB Output is correct
11 Correct 32 ms 1116 KB Output is correct
12 Correct 28 ms 1116 KB Output is correct
13 Correct 28 ms 1116 KB Output is correct
14 Correct 26 ms 1116 KB Output is correct
15 Correct 27 ms 1116 KB Output is correct
16 Correct 28 ms 1172 KB Output is correct
17 Correct 28 ms 1116 KB Output is correct
18 Correct 28 ms 1116 KB Output is correct
19 Runtime error 5 ms 2352 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 3480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 860 KB Output is correct
2 Correct 14 ms 1088 KB Output is correct
3 Correct 27 ms 1116 KB Output is correct
4 Correct 27 ms 1200 KB Output is correct
5 Correct 33 ms 1116 KB Output is correct
6 Correct 26 ms 1116 KB Output is correct
7 Correct 27 ms 1108 KB Output is correct
8 Correct 27 ms 1080 KB Output is correct
9 Correct 32 ms 1116 KB Output is correct
10 Correct 27 ms 1116 KB Output is correct
11 Correct 32 ms 1116 KB Output is correct
12 Correct 28 ms 1116 KB Output is correct
13 Correct 28 ms 1116 KB Output is correct
14 Correct 26 ms 1116 KB Output is correct
15 Correct 27 ms 1116 KB Output is correct
16 Correct 28 ms 1172 KB Output is correct
17 Correct 28 ms 1116 KB Output is correct
18 Correct 28 ms 1116 KB Output is correct
19 Runtime error 5 ms 2352 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -