Submission #1276073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276073		retr0foxx	Bubble Sort Machine (JOI25_bubble)	C++20	31 / 100	537 ms	27648 KiB

bubble

#include <iostream>
#include <algorithm>

/*
we have something which stores how many elements we have at the back

*/

#define MAXN 500005
#define int long long
#define printf
#define INF (int)(1e18)

struct query_t
{
    int t, l, r;
};

int a[MAXN];
int occ[MAXN];
query_t queries[MAXN];
int occn = 0;
int occe = 0;
int n, q;

int pref[MAXN];

signed main1()
{
    for (int i = 1; i <= n; ++i)
    {
        pref[i] = pref[i-1] + a[i];
    }
    for (int qp = 1; qp <= q; ++qp)
    {
        int t = queries[qp].t;

        if (t == 1)
        {
            for (int j = 1; j <= n-1; ++j)
            {
                if (a[j] > a[j+1]) std::swap(a[j], a[j+1]);
                pref[j] = pref[j-1] + a[j];
            }
        }
        else
        {
            int l = queries[qp].l, r = queries[qp].r;

            std::cout << pref[r] - pref[l-1] << "\n";
        }
    }
    return 0;
}

signed main3()
{
    int amount = 0;
    for (int i = n; i >= 1 && a[i] == 2; --i) ++amount;

    printf("amount: %i\n", amount);

    for (int i = 1; i <= n-amount;  ++i)
    {
        if (a[i] == 2)
        {
            occ[++occn] = i;
            printf("occ[%i] = %i\n", occn, occ[occn]);
        }
    }
    occ[++occn] = n-amount+1;
    printf("occ[%i] = %i\n", occn, occ[occn]);

    for (int qp = 1; qp <= q; ++qp)
    {
        // printf("%i, %i\n", qp, q);
        int t = queries[qp].t;

        if (t == 1)
        {
            if (occe >= occn-1) continue;
            ++occe;
        }
        else
        {
            int l = queries[qp].l, r = queries[qp].r;

            int twos = 0;

            if (occe < occn-1)
            {
                // the first index k such that data[k] - occe >= l <=> data[k] >= l + occe
                // the last index k such that data[k] - occe <= r <=> data[k] <= r + occe
                auto up = std::lower_bound(occ+occe+1, occ+occn, l + occe);
                auto down = std::upper_bound(occ+occe+1, occ+occn, r + occe);
                int hm = down - up;
                twos += hm;

                printf("bounds result: %i\n", hm);
            }
            int count_to = n - amount - occe + 1;
            twos += std::min(r - l + 1, std::max((int)0, r - count_to + 1));
            printf("count to: %i; twos=%i\n", count_to, twos);
            std::cout << r - l + 1 + twos << "\n";
        }
    }
    return 0;
}

int pmin[MAXN];
int q1cnt;
signed main2()
{
    pmin[0] = INF;
    for (int i = 1; i <= n; ++i)
    {
        pmin[i] = std::min(pmin[i-1], a[i]);
    }
    q1cnt = 1;
    for (int qp = 1; qp <= q; ++qp)
    {
        int t = queries[qp].t;
        if (t == 1)
        {
            ++q1cnt;
            q1cnt = std::min(q1cnt, n);
        }
        else
        {
            std::cout << pmin[q1cnt] << "\n";
        }
    }
    return 0;
}

int seg[4*MAXN];

void build(int l=1, int r=n, int si=1)
{
    if (l == r)
    {
        seg[si] = a[l];
        return;
    }
    int m = (l+r)/2;
    build(l, m, 2*si);
    build(m+1, r, 2*si+1);
    seg[si] = std::min(seg[2*si], seg[2*si+1]);
}

int query(int ql, int qr, int l=1, int r=n, int si=1)
{
    if (ql <= l && r <= qr) return seg[si];
    int m = (l+r)/2;
    if (ql <= m && m+1 <= qr) return std::min(query(ql, qr, l, m, 2*si), query(ql, qr, m+1, r, 2*si+1));
    if (ql <= m) return query(ql, qr, l, m, 2*si);
    return query(ql, qr, m+1, r, 2*si+1);
}

signed main4()
{
    // query at L=R=i is min[i...i+op1]
    build();

    int q1cnt = 0;
    for (int qp = 1; qp <= q; ++qp)
    {
        int t = queries[qp].t;
        if (t == 1)
        {
            ++q1cnt;
        }
        else
        {
            int idx = queries[qp].l;
            int ep = std::min(idx + q1cnt, n);
            std::cout << query(idx, ep) << "\n";
        }
    }
    return 0;
}

signed main()
{
    std::cin >> n;

    int case_three = 1;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> a[i];
        case_three = case_three && (a[i] == 1 || a[i] == 2);
    }
    std::cin >> q;
    int q1c = 0;
    int case_two = 1;
    int case_four = 1;
    for (int i = 1; i <= q; ++i)
    {
        std::cin >> queries[i].t;
        if (queries[i].t == 2)
        {
            std::cin >> queries[i].l >> queries[i].r;
            case_two = case_two && (queries[i].l == 1 && queries[i].r == 1);
            case_four = case_four && (queries[i].l == queries[i].r);
        }
        else ++q1c;
    }
    int case_one = q1c <= 10;
    if (case_three)
    {
        return main3();
    }
    else if (case_two)
    {
        printf("detected!\n");
        return main2();
    }
    else if (case_four)
    {
        printf("detected case four!\n");
        return main4();
    }
    else if (case_one)
    {
        return main1();
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 29
• Subtask 6: 0 / 17