oj.uz

Submission #1097816

# Submission time Handle Problem Language Result Execution time Memory
1097816 2024-10-08T09:47:31 Z michified Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 1191 ms 78084 KB 
#include <bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
#define lmn LLONG_MIN
#define lmx LLONG_MAX
#define imn ll_MIN
#define imx ll_MAX
using namespace std;
const ll mod = 1e9 + 7;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag, tree_order_statistics_node_update> 

ll n;

// query # elems segtree implementation begins here

vector<ordered_set> ste; // segment tree elems

void builde(vector<ll>& a, ll id, ll l, ll r) {
    if (l == r) {
        ste[id].insert(a[l]);
        return;
    }
    ll mid = (l + r) / 2;
    builde(a, lid, l, mid);
    builde(a, rid, mid + 1, r);
    for (ll elem : ste[lid]) ste[id].insert(elem);
    for (ll elem : ste[rid]) ste[id].insert(elem);
}

ll querye(ll id, ll l, ll r, ll pos, ll val) {
    if (pos < l) return 0;
    if (r <= pos) return ste[id].order_of_key(val);
    ll mid = (l + r) / 2;
    return querye(lid, l, mid, pos, val) + querye(rid, mid + 1, r, pos, val);
}

void updatee(ll id, ll l, ll r, ll pos, ll old, ll cur) {
    if (l == r) {
        ste[id].clear();
        ste[id].insert(cur);
        return;
    }
    ll mid = (l + r) / 2;
    if (pos <= mid) updatee(lid, l, mid, pos, old, cur);
    else updatee(rid, mid + 1, r, pos, old, cur);
    ste[id].erase(old);
    ste[id].insert(cur);
}

// query # elems segtree implementation ends here

// ... // 

// query min element segtree implementation begins here

vector<ll> stmin;

void buildm(vector<ll>& a, ll id, ll l, ll r) {
    if (l == r) {
        stmin[id] = a[l];
        return;
    }
    ll mid = (l + r) / 2;
    buildm(a, lid, l, mid);
    buildm(a, rid, mid + 1, r);
    stmin[id] = min(stmin[lid], stmin[rid]);
}

ll querym(ll id, ll l, ll r, ll val) {
    if (stmin[id] > val) return l;
    if (l == r) return l + 1;
    ll mid = (l + r) / 2;
    ll res = querym(rid, mid + 1, r, val);
    if (res == mid + 1) return querym(lid, l, mid, val);
    return res;
}

void updatem(ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        stmin[id] = val;
        return;
    }
    ll mid = (l + r) / 2;
    if (pos <= mid) updatem(lid, l, mid, pos, val);
    else updatem(rid, mid + 1, r, pos, val);
    stmin[id] = min(stmin[lid], stmin[rid]);
}

// query min element segtree implementation ends here

// ... //

// query ans segtree implementation begins here

vector<ll> st, lazy;

void build(vector<ll>& a, ll id, ll l, ll r) {
    if (l == r) {
        st[id] = a[l];
        return;
    }
    ll mid = (l + r) / 2;
    build(a, lid, l, mid);
    build(a, rid, mid + 1, r);
    st[id] = max(st[lid], st[rid]);
}

void pd(ll id, ll l, ll mid, ll r) {
    st[lid] += lazy[id];
    st[rid] += lazy[id];
    lazy[lid] += lazy[id];
    lazy[rid] += lazy[id];
    lazy[id] = 0;
}

void update(ll id, ll l, ll r, ll ul, ll val) {
    if (r < ul) return;
    if (l >= ul) {
        st[id] += val;
        lazy[id] += val;
        return;
    }
    ll mid = (l + r) / 2;
    pd(id, l, mid, r);
    update(lid, l, mid, ul, val);
    update(rid, mid + 1, r, ul, val);
    st[id] = max(st[lid], st[rid]);
}

void clazy(ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        st[id] = l - querye(0, 0, n - 1, pos - 1, val);
        return;
    }
    ll mid = (l + r) / 2;
    pd(id, l, mid, r);
    if (pos <= mid) clazy(lid, l, mid, pos, val);
    else clazy(rid, mid + 1, r, pos, val);
    st[id] = max(st[lid], st[rid]);
}

void replace(vector<ll>& a, ll pos, ll val) {
    update(0, 0, n - 1, querym(0, 0, n - 1, a[pos]), 1);
    updatem(0, 0, n - 1, pos, val);
    updatee(0, 0, n - 1, pos, a[pos], val);
    a[pos] = val;
    update(0, 0, n - 1, querym(0, 0, n - 1, val), -1);
    clazy(0, 0, n - 1, pos, val);
}

void init(vector<ll>& a) {
    st.resize(n * 4);
    lazy.resize(n * 4);
    vector<ll> inp(n);
    for (ll i = 0; i < n; i++) inp[i] = i - querye(0, 0, n - 1, i - 1, a[i]);
    build(inp, 0, 0, n - 1);
}

// query ans segtree implementations ends here

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	n = A.size();
    ll q = X.size(), i;
    vector<ll> a(n);
    for (i = 0; i < n; i++) a[i] = A[i] * 1000000ll + i;
    stmin.resize(n * 4);
    ste.resize(n * 4);
    buildm(a, 0, 0, n - 1);
    builde(a, 0, 0, n - 1);
    init(a);
    vector<int> ans(q);
    for (i = 0; i < q; i++) {
        replace(a, X[i], V[i] * 1000000ll + X[i]);
        ans[i] = st[0];
    }
    return ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 41112 KB Output is correct
2 Correct 570 ms 61252 KB Output is correct
3 Correct 1156 ms 78084 KB Output is correct
4 Correct 1020 ms 77904 KB Output is correct
5 Correct 1104 ms 77908 KB Output is correct
6 Correct 1131 ms 77908 KB Output is correct
7 Correct 1124 ms 77900 KB Output is correct
8 Correct 1145 ms 77904 KB Output is correct
9 Correct 1191 ms 77904 KB Output is correct
10 Correct 698 ms 77908 KB Output is correct
11 Correct 778 ms 78056 KB Output is correct
12 Correct 693 ms 77908 KB Output is correct
13 Correct 577 ms 77904 KB Output is correct
14 Correct 581 ms 77992 KB Output is correct
15 Correct 602 ms 78020 KB Output is correct
16 Correct 468 ms 77904 KB Output is correct
17 Correct 473 ms 77908 KB Output is correct
18 Correct 468 ms 77908 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -