Submission #1097856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097856		michified	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3724 ms	144196 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, m;

// segtree implementation begins here

vector<int> st, lazy;

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 ur, int val) {
    if (r < ul or l > ur) return;
    if (ul <= l and r <= ur) {
        st[id] += val;
        lazy[id] += val;
        return;
    }
    int mid = (l + r) / 2;
    pd(id, l, mid, r);
    update(lid, l, mid, ul, ur, val);
    update(rid, mid + 1, r, ul, ur, val);
    st[id] = max(st[lid], st[rid]);
}

void setas(int id, int l, int r, int pos, int val) {
    if (l == r) {
        st[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    pd(id, l, mid, r);
    if (pos <= mid) setas(lid, l, mid, pos, val);
    else setas(rid, mid + 1, r, pos, val);
    st[id] = max(st[lid], st[rid]);
}

// 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;
    unordered_map<ll, int> b2s;
    vector<ll> s2b = a;
    for (i = 0; i < q; i++) s2b.push_back(V[i] * 1000000ll + X[i]);
    sort(s2b.begin(), s2b.end());
    for (i = 0; i < n + q; i++) b2s[s2b[i]] = i;
    m = s2b.size();
    st.resize(m * 4, -1e9);
    lazy.resize(m * 4);
    ordered_set os;
    for (ll elem : a) os.insert(elem);
    for (i = 0; i < n; i++) setas(0, 0, m - 1, b2s[a[i]], i - os.order_of_key(a[i]));
    vector<int> ans(q);
    for (i = 0; i < q; i++) {
        update(0, 0, m - 1, b2s[a[X[i]]] + 1, m - 1, 1);
        os.erase(a[X[i]]);
        setas(0, 0, m - 1, b2s[a[X[i]]], -1e9);
        a[X[i]] = V[i] * 1000000ll + X[i];
        os.insert(a[X[i]]);
        setas(0, 0, m - 1, b2s[a[X[i]]], X[i] - os.order_of_key(a[X[i]]));
        update(0, 0, m - 1, b2s[a[X[i]]] + 1, m - 1, -1);
        ans[i] = st[0];
    }
    return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40