Submission #1028190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028190		BABY_GANGSTER	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	973 ms	46768 KiB

bubblesort2

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
 
constexpr int64_t N = 500000, L = 1 << 20;
 
int32_t T[2 * L][3];
 
void propagate(size_t k)
{
    T[2 * k][0] += T[k][1];
    T[2 * k][1] += T[k][1];
    T[2 * k + 1][0] += T[k][1];
    T[2 * k + 1][1] += T[k][1];
    T[k][1] = 0;
}
 
void increment(size_t i, size_t j, int64_t x, size_t k = 1, size_t a = 0, size_t b = L)
{
    if (b <= i || a >= j)
        return;
    if (i <= a && b <= j)
        T[k][0] += x, T[k][1] += x;
    else
    {
        propagate(k);
        increment(i, j, x, 2 * k, a, (a + b) / 2);
        increment(i, j, x, 2 * k + 1, (a + b) / 2, b);
        T[k][0] = max(T[2 * k][0], T[2 * k + 1][0]);
        T[k][2] = T[2 * k][2] + T[2 * k + 1][2];
    }
}
 
void update(size_t i, int64_t x, size_t k = 1, size_t a = 0, size_t b = L)
{
    if (b - a == 1)
    {
        T[k][0] = x;
        T[k][2] = x != INT32_MIN / 2;
    }
    else
    {
        propagate(k);
        if (i < (a + b) / 2)
            update(i, x, 2 * k, a, (a + b) / 2);
        else
            update(i, x, 2 * k + 1, (a + b) / 2, b);
        T[k][0] = max(T[2 * k][0], T[2 * k + 1][0]);
        T[k][2] = T[2 * k][2] + T[2 * k + 1][2];
    }
}
 
int64_t num_elements(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L)
{
    if (b <= i || a >= j)
        return 0;
    if (i <= a && b <= j)
        return T[k][2];
    return num_elements(i, j, 2 * k, a, (a + b) / 2) +
           num_elements(i, j, 2 * k + 1, (a + b) / 2, b);
}
 
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
    vector<size_t> coords;
    for (size_t i = 0; i < A.size(); i++)
        coords.push_back(A[i] * N + i);
    for (size_t i = 0; i < X.size(); i++)
        coords.push_back(V[i] * N + X[i]);
    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());
    for (size_t i = 0; i < A.size(); i++)
        A[i] = lower_bound(coords.begin(), coords.end(), A[i] * N + i) - coords.begin();
    for (size_t i = 0; i < X.size(); i++)
        V[i] = lower_bound(coords.begin(), coords.end(), V[i] * N + X[i]) - coords.begin();
 
    for (size_t i = L; i < 2 * L; i++)
        T[i][0] = INT32_MIN / 2;
    for (size_t i = 0; i < A.size(); i++)
        T[L + A[i]][2] = 1;
    for (size_t i = L - 1; i; i--)
        T[i][2] = T[2 * i][2] + T[2 * i + 1][2];
    for (size_t i = 0; i < A.size(); i++)
        T[L + A[i]][0] = (int64_t)i - num_elements(0, A[i]);
    for (size_t i = L - 1; i; i--)
        T[i][0] = max(T[2 * i][0], T[2 * i + 1][0]);
 
    vector<int> ans(X.size());
    for (size_t i = 0; i < X.size(); i++)
    {
        update(A[X[i]], INT32_MIN / 2);
        increment(A[X[i]], L, 1);
        A[X[i]] = V[i];
        increment(A[X[i]], L, -1);
        update(A[X[i]], X[i] - num_elements(0, A[X[i]]));
        ans[i] = T[1][0];
    }
 
    return ans;
}
 

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