Submission #1097794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097794		michified	Bubble Sort 2 (JOI18_bubblesort2)	C++17	22 / 100	1376 ms	77140 KiB

bubblesort2

#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 (int elem : ste[lid]) ste[id].insert(elem);
    for (int 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
• Subtask 2: 0 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40