oj.uz

Submission #1097803

# Submission time Handle Problem Language Result Execution time Memory
1097803 2024-10-08T09:42:28 Z michified Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 1276 ms 76372 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 INT_MIN
#define imx INT_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> 

int n;

// query # elems segtree implementation begins here

vector<ordered_set> ste; // segment tree elems

void builde(vector<ll>& a, int id, int l, int r) {
    if (l == r) {
        ste[id].insert(a[l]);
        return;
    }
    int 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);
}

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

void updatee(int id, int l, int r, int pos, ll old, ll cur) {
    if (l == r) {
        ste[id].clear();
        ste[id].insert(cur);
        return;
    }
    int 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 build(vector<ll>& a, int id, int l, int r) {
    if (l == r) {
        stmin[id] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(a, lid, l, mid);
    build(a, rid, mid + 1, r);
    stmin[id] = min(stmin[lid], stmin[rid]);
}

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

void updatem(int id, int l, int r, int pos, ll val) {
    if (l == r) {
        stmin[id] = val;
        return;
    }
    int 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<int> st, lazy;

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

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

void update(int id, int l, int r, int ul, int val) {
    if (r < ul) return;
    if (l >= ul) {
        st[id] += val;
        lazy[id] += val;
        return;
    }
    int 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(int id, int l, int r, int pos, ll val) {
    if (l == r) {
        st[id] = l - querye(0, 0, n - 1, pos - 1, val);
        return;
    }
    int 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, int 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<int> inp(n);
    for (int 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();
    int 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);
    build(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 856 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 856 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 117 ms 40052 KB Output is correct
2 Correct 568 ms 59828 KB Output is correct
3 Correct 1254 ms 76172 KB Output is correct
4 Correct 1162 ms 76332 KB Output is correct
5 Correct 1196 ms 76368 KB Output is correct
6 Correct 1249 ms 76368 KB Output is correct
7 Correct 1183 ms 76368 KB Output is correct
8 Correct 1276 ms 76368 KB Output is correct
9 Correct 1154 ms 76372 KB Output is correct
10 Correct 709 ms 76320 KB Output is correct
11 Correct 640 ms 76332 KB Output is correct
12 Correct 652 ms 76368 KB Output is correct
13 Correct 527 ms 76372 KB Output is correct
14 Correct 606 ms 76364 KB Output is correct
15 Correct 606 ms 76368 KB Output is correct
16 Correct 467 ms 76368 KB Output is correct
17 Correct 461 ms 76176 KB Output is correct
18 Correct 451 ms 76200 KB Output is correct

Subtask #4
0 / 40.0

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