oj.uz

Submission #1097855

# Submission time Handle Problem Language Result Execution time Memory
1097855 2024-10-08T11:53:15 Z michified Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 9164 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, 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++) {
        for (int j = b2s[a[X[i]]] + 1; j < m; j++) update(0, 0, m - 1, j, j, 1);
        //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]]));
        for (int j = b2s[a[X[i]]] + 1; j < m; j++) update(0, 0, m - 1, j, j, -1);
        //update(0, 0, m - 1, b2s[a[X[i]]] + 1, m - 1, -1);
        ans[i] = st[0];
    }
    return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 348 KB Output is correct
2 Correct 121 ms 604 KB Output is correct
3 Correct 724 ms 860 KB Output is correct
4 Correct 731 ms 976 KB Output is correct
5 Correct 717 ms 1108 KB Output is correct
6 Correct 561 ms 860 KB Output is correct
7 Correct 611 ms 984 KB Output is correct
8 Correct 650 ms 972 KB Output is correct
9 Correct 719 ms 860 KB Output is correct
10 Correct 657 ms 1108 KB Output is correct
11 Correct 657 ms 860 KB Output is correct
12 Correct 668 ms 860 KB Output is correct
13 Correct 723 ms 860 KB Output is correct
14 Correct 700 ms 948 KB Output is correct
15 Correct 692 ms 860 KB Output is correct
16 Correct 781 ms 952 KB Output is correct
17 Correct 750 ms 1104 KB Output is correct
18 Correct 748 ms 936 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 348 KB Output is correct
2 Correct 121 ms 604 KB Output is correct
3 Correct 724 ms 860 KB Output is correct
4 Correct 731 ms 976 KB Output is correct
5 Correct 717 ms 1108 KB Output is correct
6 Correct 561 ms 860 KB Output is correct
7 Correct 611 ms 984 KB Output is correct
8 Correct 650 ms 972 KB Output is correct
9 Correct 719 ms 860 KB Output is correct
10 Correct 657 ms 1108 KB Output is correct
11 Correct 657 ms 860 KB Output is correct
12 Correct 668 ms 860 KB Output is correct
13 Correct 723 ms 860 KB Output is correct
14 Correct 700 ms 948 KB Output is correct
15 Correct 692 ms 860 KB Output is correct
16 Correct 781 ms 952 KB Output is correct
17 Correct 750 ms 1104 KB Output is correct
18 Correct 748 ms 936 KB Output is correct
19 Execution timed out 9031 ms 2392 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7786 ms 5136 KB Output is correct
2 Execution timed out 9029 ms 9164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 348 KB Output is correct
2 Correct 121 ms 604 KB Output is correct
3 Correct 724 ms 860 KB Output is correct
4 Correct 731 ms 976 KB Output is correct
5 Correct 717 ms 1108 KB Output is correct
6 Correct 561 ms 860 KB Output is correct
7 Correct 611 ms 984 KB Output is correct
8 Correct 650 ms 972 KB Output is correct
9 Correct 719 ms 860 KB Output is correct
10 Correct 657 ms 1108 KB Output is correct
11 Correct 657 ms 860 KB Output is correct
12 Correct 668 ms 860 KB Output is correct
13 Correct 723 ms 860 KB Output is correct
14 Correct 700 ms 948 KB Output is correct
15 Correct 692 ms 860 KB Output is correct
16 Correct 781 ms 952 KB Output is correct
17 Correct 750 ms 1104 KB Output is correct
18 Correct 748 ms 936 KB Output is correct
19 Execution timed out 9031 ms 2392 KB Time limit exceeded
20 Halted 0 ms 0 KB -