Submission #531807

#	Time	Username	Problem	Language	Result	Execution time	Memory
531807		Servus2022	Index (COCI21_index)	C++14	110 / 110	851 ms	9924 KiB

index

#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 2e5 + 5;

int Bucket;
struct intrebare {
	int L, R;
	int ind;

	bool operator < (const intrebare &other) const {
		return (L / Bucket < other.L / Bucket) || (L / Bucket == other.L / Bucket && R < other.R);
	}
};

intrebare quer[NMAX];

int N, Q;

int aib[NMAX];
int A[NMAX];

void Update (int pos, int val) {
	for (int i = pos; i <= N; i += ub(i))
		aib[i] += val;
}

int Query (int pos) {
	int S = 0;

	for (int i = pos; i; i -= ub(i))
		S += aib[i];

	return S;
}

void Read () {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N >> Q;

	Bucket = Q / sqrt(N);
	for (int i = 1; i <= N; ++ i )
		cin >> A[i];

	for (int i = 1; i <= Q; ++ i ) {
		cin >> quer[i].L >> quer[i].R;
		quer[i].ind = i;
	}

	sort(quer+1, quer+Q+1);
}

int sol[NMAX];

void Add (int pos) {
	Update(A[pos], +1);
}

void Elimin (int pos) {
	Update(A[pos], -1);
}

int Raspuns (int Total) {
    int st = 1, dr = N;
	int ans = 1;

    while (st <= dr) {
		int mij = (st + dr) / 2;
		int cnt = Query(mij-1);

		if (Total - cnt >= mij) {
			st = mij + 1;
			ans = mij;
		}
		else dr = mij - 1;
    }

    return ans;
}

/*
dp[i][j] - i cifre cu ultimele 4 cifre j
dp[i][j] = max(dp[i-1][jprim]) + 1 (j este lucky)

i cifre :     a b c m
i-1 cifre:  n a b c

dp[i][j][k][l][m] = max(dp[i-1][aux][j][k][l]) + 1
*/


void Solve () {
    int st = 1, dr = 0;

    for (int i = 1; i <= Q; ++ i ) {
        while (dr < quer[i].R) {
            ++ dr;
            Add(dr);
        }

        while (st > quer[i].L) {
			-- st;
			Add(st);
        }

        while (st < quer[i].L) {
			Elimin(st);
			++ st;
        }

        while (dr > quer[i].R) {
			Elimin(dr);
			-- dr;
        }

        sol[quer[i].ind] = Raspuns(quer[i].R - quer[i].L + 1);
    }

    for (int i = 1; i <= Q; ++ i )
		cout << sol[i] << '\n';
}

int main () {
	Read();
	Solve();

	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50