Submission #1254378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254378		chikien2009	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1079 ms	38624 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

// void setup()
// {
// #ifndef ONLINE_JUDGE
//     freopen("test.inp", "r", stdin); 
//     freopen("test.out", "w", stdout);
// #endif
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);
// }

int n, tree[4000000], rem[4000000];  
pair<int, int> p[1000000];

inline void Update(int ind, int l, int r, int x, int y, int v)
{
    if (y < x || r < x || y < l)
    {
        return;
    }
    if (x <= l && r <= y)
    {
        rem[ind] += v;
        tree[ind] += v;
        return;
    }
    int m = (l + r) >> 1;
    Update(ind << 1, l, m, x, y, v);
    Update(ind << 1 | 1, m + 1, r, x, y, v);
    tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]) + rem[ind];
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
    vector<int> res;
    for (int i = 0; i < A.size(); ++i)
    {
        p[n++] = {A[i], i};
    }
    for (int i = 0; i < V.size(); ++i)
    {
        p[n++] = {V[i], X[i]};
    }
    sort(p, p + n);
    n = unique(p, p + n) - p;
    for (int i = 0; i < A.size(); ++i)
    {
        A[i] = lower_bound(p, p + n, make_pair(A[i], i)) - p + 1;
        Update(1, 1, n, A[i], A[i], i);
        Update(1, 1, n, A[i] + 1, n, -1);
    }
    for (int i = 0; i < V.size(); ++i)
    {
        V[i] = lower_bound(p, p + n, make_pair(V[i], X[i])) - p + 1;
        Update(1, 1, n, A[X[i]], A[X[i]], -X[i]);
        Update(1, 1, n, A[X[i]] + 1, n, 1);
        Update(1, 1, n, V[i], V[i], X[i]);
        Update(1, 1, n, V[i] + 1, n, -1);
        A[X[i]] = V[i];
        res.push_back(tree[1]);
    }
    return res;
}

// int main()
// {
//     setup();

//     return 0;
// }

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