제출 #1276059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276059		retr0foxx	Bubble Sort Machine (JOI25_bubble)	C++20	15 / 100	817 ms	7504 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

int a[MAXN];
int occ[MAXN];
int occn = 0;
int occe = 0;

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

    int case_three = 0;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> a[i];
        case_three = case_three && (a[i] == 1 || a[i] == 2);
    }
    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]);

    int q;
    std::cin >> q;
    while (q--)
    {
        int t;
        std::cin >> t;

        if (t == 1)
        {
            if (occe >= occn-1) continue;
            ++occe;
        }
        else
        {
            int l, r;
            std::cin >> l >> 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;
}

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