oj.uz

Submission #1097794

# Submission time Handle Problem Language Result Execution time Memory
1097794 2024-10-08T09:37:27 Z michified Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 1376 ms 77140 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 (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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1112 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 1112 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 116 ms 40204 KB Output is correct
2 Correct 521 ms 60108 KB Output is correct
3 Correct 1058 ms 76884 KB Output is correct
4 Correct 1328 ms 76928 KB Output is correct
5 Correct 1376 ms 76840 KB Output is correct
6 Correct 1226 ms 76844 KB Output is correct
7 Correct 1240 ms 76936 KB Output is correct
8 Correct 1341 ms 76832 KB Output is correct
9 Correct 1111 ms 76944 KB Output is correct
10 Correct 652 ms 76944 KB Output is correct
11 Correct 642 ms 77020 KB Output is correct
12 Correct 649 ms 76944 KB Output is correct
13 Correct 557 ms 76940 KB Output is correct
14 Correct 555 ms 76884 KB Output is correct
15 Correct 572 ms 77012 KB Output is correct
16 Correct 463 ms 76944 KB Output is correct
17 Correct 457 ms 77140 KB Output is correct
18 Correct 435 ms 77004 KB Output is correct

Subtask #4
0 / 40.0

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