Submission #1307351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307351		retr0foxx	Abracadabra (CEOI22_abracadabra)	C++20	25 / 100	3096 ms	7204 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

#define printff
#define printf
//#define printff(string, ...) printf(string, ##__VA_ARGS__); fflush(stdout)
#define MAXN 200000
#define LOG 19

int n, q;
int pos[MAXN+5];
int data[MAXN+5];
int next[MAXN+5];
int size[MAXN+5];
int sizer[MAXN+5];

void fwadd(int i, int x)
{
    sizer[i] += x;
    while (i <= n)
    {
        size[i] += x;
        i += i & -i;
    }
}

int fwget(int i)
{
    int res = 0;
    while (i >= 1)
    {
        res += size[i];
        i -= i & -i;
    }
    return res;
}

#define pii std::pair<int, int>

// the last index i such that pref[i] <= n/2
pii fwsearch(int v=n/2)
{
    int cur = 0;
    int curs = 0;
    for (int p = LOG-1; p >= 0; --p)
    {
        int nxc = cur + (1 << p);
        if (nxc > n || curs + size[nxc] > v) continue;
        curs += size[nxc];
        cur = nxc;
    }
    return pii(cur, curs);
}

int gvcur = 0, gvcurs = 0;

int getvalue(int v=n/2+1)
{
	printf("state (v=%i): ");
	for (int i = 1; i <= n; ++i)
		printf("%i ", fwget(i) - (i == 1 ? 0 : fwget(i-1)));
	printf("\n");

    int cur = 0;
    int curs = 0;
    for (int p = LOG-1; p >= 0; --p)
    {
        int nxc = cur + (1 << p);
        if (nxc > n || curs + size[nxc] >= v) continue;
        curs += size[nxc];
        cur = nxc;
    }
	printff("detected cur: %i\n", cur);
    cur++;
    gvcur = cur;
    gvcurs = curs;
    return data[pos[cur] + v - curs - 1];
}


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

query_t queries[MAXN+5];
int res[MAXN+5];

signed main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
    //printff("apakah sampai sini\n");
    std::cin >> n >> q;

    //printff("apakah sampai sini\n");
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> data[i];
        pos[data[i]] = i;
        next[i] = n+1;
        //printf("apakah sampai sini\n");
    }
    next[n+1] = n+1;

    std::vector<int> stack;
    for (int i = 1; i <= n; ++i)
    {
        while (stack.size() && data[stack.back()] < data[i])
        {
            next[stack.back()] = i;
            stack.pop_back();
        }
        stack.push_back(i);
    }

    for (int i = 1; i <= q; ++i)
    {
        std::cin >> queries[i].t >> queries[i].i;
        queries[i].r = i;
    }
    std::sort(queries+1, queries+1+q, [](const query_t &a, const query_t &b){ return a.t < b.t; });
    int qp = 1;
    while (qp <= q && queries[qp].t == 0)
    {
        res[queries[qp].r] = data[queries[qp].i];
        ++qp;
    }

    int cur = 1;
    while (cur != n+1)
    {
        fwadd(data[cur], next[cur] - cur);
        printff("cur: %i\n", cur);
        cur = next[cur];
    }
    printff("done with that\n");

    int k = 1;
    while (1)
    {
        // lb = last_block, totalsize/index
        int now = getvalue();
        if (sizer[now] != 0) break;
		// 7 5 2 9 10 | 8 4 3 6 1

        int last_index = pos[gvcur] + sizer[gvcur] - 1;
        printff("last pos: %i, cur: %i, size: %i, us: %i, last index: %i, sub index: %i\n", pos[gvcur], gvcur, sizer[gvcur], gvcurs, last_index, now);
		fwadd(gvcur, -(gvcurs + sizer[gvcur] - n/2));
        while (1)
        {
            int now2i = std::min(next[pos[now]], last_index + 1);
			printf("at current position (position %i): %i, next position: %i (contains %i)\n", pos[now], now, now2i, data[now2i]);
            fwadd(now, now2i - pos[now]);
			if (now2i > last_index) break;
            now = data[now2i];
        }
        while (qp <= q && queries[qp].t <= k)
        {
            res[queries[qp].r] = getvalue(queries[qp].i);
            ++qp;
        }
		++k;
        /*int A = sizer[gvcur]-(pos[now]-pos[gvcur]);
        fwadd(gvcur,-A);        
        while (true)
        {
            int now2 = data[next[pos[now]]];
            int B = pos[now2]-pos[now];
            if (B >= A) break;
            fwadd(now,B);
            A -= B;
            now = now2;
        }
        fwadd(now,A);*/
        // @---@----@--|----@----
        // sssssssss
    }
    while (qp <= q)
    {
        res[queries[qp].r] = getvalue(queries[qp].i);
        ++qp;
    }
    for (int i = 1; i <= q; ++i)
        std::cout << res[i] << "\n";

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25