oj.uz

Submission #1013734

# Submission time Handle Problem Language Result Execution time Memory
1013734 2024-07-04T05:04:51 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 3252 ms 163996 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 = 1E6+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;
    }
};

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    struct Node {
        ll val;
        bool hasL;
        ll lazy;
        bool isIdem;

        Node (): isIdem(true) {}
        Node (ll val): val(val), hasL(false), lazy(0), isIdem(false) {}

        Node operator+ (const Node &o) const {
            if (isIdem) return o;
            if (o.isIdem) return *this;
            return Node(max(val, o.val));
        }
    };
    vector <Node> tree;
    ll n;

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

    void push (ll l, ll r, ll id) {
        if (!tree[id].hasL) return;
        tree[id].val += tree[id].lazy;
        if (l < r) {
            tree[id+1].hasL = true;
            tree[id+1].lazy += tree[id].lazy;
            tree[id+off].hasL = true;
            tree[id+off].lazy += tree[id].lazy;
        }
        tree[id].hasL = false;
        tree[id].lazy = 0;
    }

    void set (ll at, ll val) { set(at, val, 0, n-1, 0); }
    void set (ll at, ll val, ll l, ll r, ll id) {
        push(l, r, id);
        if (at < l || r < at) return;
        if (at <= l && r <= at) {
            tree[id].val = val;
            push(l, r, id);
            return;
        }
        set(at, val, l, mid, id+1);
        set(at, val, mid+1, r, id+off);
        tree[id] = tree[id+1] + tree[id+off];
    }

    void update (ll ql, ll qr, ll val) { update(ql, qr, val, 0, n-1, 0); }
    void update (ll ql, ll qr, ll val, ll l, ll r, ll id) {
        push(l, r, id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[id].hasL = true;
            tree[id].lazy = val;
            push(l, r, id);
            return;
        }
        update(ql, qr, val, l, mid, id+1);
        update(ql, qr, val, mid+1, r, id+off);
        tree[id] = tree[id+1] + tree[id+off];
    }

    ll query (ll ql, ll qr) { return query(ql, qr, 0, n-1, 0).val; }
    Node query (ll ql, ll qr, ll l, ll r, ll id) {
        push(l, r, id);
        if (qr < l || r < ql) return Node();
        if (ql <= l && r <= qr) return tree[id];
        return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
    }
};

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);
    }
    for (ll i = 0; i < MAXN; i++) {
        stAns.set(i, -INF);
    }
    auto redo = [&](ll i) {
        while (pq[i].size() && ve[pq[i].top()] != i) pq[i].pop();
        stAns.set(i, -INF);
        if (!pq[i].size()) return;
        stAns.set(i, pq[i].top()+1 - ftFreq.query(i));
    };
    for (ll i = 0; i < n+wh.size(); i++) redo(i);
    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);
        ans.push_back(stAns.query(0, MAXN-8));
    }
    return ans;
}

Compilation message

bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:130:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'long long unsigned int' [-Wsign-compare]
  130 |     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 319 ms 102228 KB Output is correct
2 Correct 337 ms 102232 KB Output is correct
3 Correct 340 ms 102312 KB Output is correct
4 Correct 315 ms 102224 KB Output is correct
5 Correct 362 ms 102224 KB Output is correct
6 Correct 372 ms 102228 KB Output is correct
7 Correct 334 ms 102240 KB Output is correct
8 Correct 377 ms 102316 KB Output is correct
9 Correct 331 ms 102480 KB Output is correct
10 Correct 335 ms 102332 KB Output is correct
11 Correct 330 ms 102316 KB Output is correct
12 Correct 358 ms 102308 KB Output is correct
13 Correct 345 ms 102228 KB Output is correct
14 Correct 339 ms 102332 KB Output is correct
15 Correct 337 ms 102228 KB Output is correct
16 Correct 344 ms 102316 KB Output is correct
17 Correct 342 ms 102216 KB Output is correct
18 Correct 346 ms 102192 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 102228 KB Output is correct
2 Correct 337 ms 102232 KB Output is correct
3 Correct 340 ms 102312 KB Output is correct
4 Correct 315 ms 102224 KB Output is correct
5 Correct 362 ms 102224 KB Output is correct
6 Correct 372 ms 102228 KB Output is correct
7 Correct 334 ms 102240 KB Output is correct
8 Correct 377 ms 102316 KB Output is correct
9 Correct 331 ms 102480 KB Output is correct
10 Correct 335 ms 102332 KB Output is correct
11 Correct 330 ms 102316 KB Output is correct
12 Correct 358 ms 102308 KB Output is correct
13 Correct 345 ms 102228 KB Output is correct
14 Correct 339 ms 102332 KB Output is correct
15 Correct 337 ms 102228 KB Output is correct
16 Correct 344 ms 102316 KB Output is correct
17 Correct 342 ms 102216 KB Output is correct
18 Correct 346 ms 102192 KB Output is correct
19 Correct 388 ms 102664 KB Output is correct
20 Correct 353 ms 102936 KB Output is correct
21 Correct 383 ms 103136 KB Output is correct
22 Correct 365 ms 102940 KB Output is correct
23 Correct 371 ms 102940 KB Output is correct
24 Correct 362 ms 102856 KB Output is correct
25 Correct 374 ms 102936 KB Output is correct
26 Correct 384 ms 102940 KB Output is correct
27 Correct 346 ms 102936 KB Output is correct
28 Correct 372 ms 103108 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 103316 KB Output is correct
2 Correct 450 ms 104540 KB Output is correct
3 Correct 476 ms 105656 KB Output is correct
4 Correct 511 ms 105560 KB Output is correct
5 Correct 491 ms 105916 KB Output is correct
6 Correct 484 ms 105592 KB Output is correct
7 Correct 503 ms 105708 KB Output is correct
8 Correct 489 ms 105652 KB Output is correct
9 Correct 468 ms 105652 KB Output is correct
10 Correct 488 ms 105916 KB Output is correct
11 Correct 487 ms 105912 KB Output is correct
12 Correct 499 ms 105916 KB Output is correct
13 Correct 493 ms 105576 KB Output is correct
14 Correct 462 ms 105404 KB Output is correct
15 Correct 469 ms 105576 KB Output is correct
16 Correct 504 ms 105304 KB Output is correct
17 Correct 485 ms 105396 KB Output is correct
18 Correct 485 ms 105396 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 102228 KB Output is correct
2 Correct 337 ms 102232 KB Output is correct
3 Correct 340 ms 102312 KB Output is correct
4 Correct 315 ms 102224 KB Output is correct
5 Correct 362 ms 102224 KB Output is correct
6 Correct 372 ms 102228 KB Output is correct
7 Correct 334 ms 102240 KB Output is correct
8 Correct 377 ms 102316 KB Output is correct
9 Correct 331 ms 102480 KB Output is correct
10 Correct 335 ms 102332 KB Output is correct
11 Correct 330 ms 102316 KB Output is correct
12 Correct 358 ms 102308 KB Output is correct
13 Correct 345 ms 102228 KB Output is correct
14 Correct 339 ms 102332 KB Output is correct
15 Correct 337 ms 102228 KB Output is correct
16 Correct 344 ms 102316 KB Output is correct
17 Correct 342 ms 102216 KB Output is correct
18 Correct 346 ms 102192 KB Output is correct
19 Correct 388 ms 102664 KB Output is correct
20 Correct 353 ms 102936 KB Output is correct
21 Correct 383 ms 103136 KB Output is correct
22 Correct 365 ms 102940 KB Output is correct
23 Correct 371 ms 102940 KB Output is correct
24 Correct 362 ms 102856 KB Output is correct
25 Correct 374 ms 102936 KB Output is correct
26 Correct 384 ms 102940 KB Output is correct
27 Correct 346 ms 102936 KB Output is correct
28 Correct 372 ms 103108 KB Output is correct
29 Correct 357 ms 103316 KB Output is correct
30 Correct 450 ms 104540 KB Output is correct
31 Correct 476 ms 105656 KB Output is correct
32 Correct 511 ms 105560 KB Output is correct
33 Correct 491 ms 105916 KB Output is correct
34 Correct 484 ms 105592 KB Output is correct
35 Correct 503 ms 105708 KB Output is correct
36 Correct 489 ms 105652 KB Output is correct
37 Correct 468 ms 105652 KB Output is correct
38 Correct 488 ms 105916 KB Output is correct
39 Correct 487 ms 105912 KB Output is correct
40 Correct 499 ms 105916 KB Output is correct
41 Correct 493 ms 105576 KB Output is correct
42 Correct 462 ms 105404 KB Output is correct
43 Correct 469 ms 105576 KB Output is correct
44 Correct 504 ms 105304 KB Output is correct
45 Correct 485 ms 105396 KB Output is correct
46 Correct 485 ms 105396 KB Output is correct
47 Correct 1018 ms 120512 KB Output is correct
48 Correct 3043 ms 158632 KB Output is correct
49 Correct 3226 ms 163756 KB Output is correct
50 Correct 3196 ms 163712 KB Output is correct
51 Correct 3088 ms 163724 KB Output is correct
52 Correct 3252 ms 163892 KB Output is correct
53 Correct 3141 ms 163804 KB Output is correct
54 Correct 3085 ms 163996 KB Output is correct
55 Correct 3062 ms 163964 KB Output is correct
56 Correct 2930 ms 163964 KB Output is correct
57 Correct 3126 ms 163872 KB Output is correct
58 Correct 2959 ms 163916 KB Output is correct
59 Correct 2905 ms 158764 KB Output is correct
60 Correct 2918 ms 158848 KB Output is correct
61 Correct 2993 ms 158772 KB Output is correct
62 Correct 2798 ms 156720 KB Output is correct
63 Correct 2777 ms 156792 KB Output is correct
64 Correct 2783 ms 156756 KB Output is correct
65 Correct 2578 ms 154496 KB Output is correct
66 Correct 2615 ms 154568 KB Output is correct
67 Correct 2668 ms 154644 KB Output is correct