CSES - Putka Open 2025 – 3/5

Submission details
Task:	Kyselyt
Sender:	hltk
Submission time:	2025-10-18 11:06:03 +0300
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	20
#3	ACCEPTED	30
#4	ACCEPTED	40

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1, 2, 3, 4	details
#2	ACCEPTED	0.02 s	1, 2, 3, 4	details
#3	ACCEPTED	0.02 s	1, 3, 4	details
#4	ACCEPTED	0.28 s	2, 3, 4	details
#5	ACCEPTED	0.31 s	2, 3, 4	details
#6	ACCEPTED	0.16 s	2, 3, 4	details
#7	ACCEPTED	0.20 s	3, 4	details
#8	ACCEPTED	0.60 s	4	details
#9	ACCEPTED	0.67 s	4	details
#10	ACCEPTED	0.42 s	4	details
#11	ACCEPTED	0.27 s	3, 4	details
#12	ACCEPTED	0.57 s	4	details
#13	ACCEPTED	0.16 s	3, 4	details
#14	ACCEPTED	0.32 s	4	details
#15	ACCEPTED	0.40 s	4	details
#16	ACCEPTED	0.52 s	4	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:47:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                 for (int j = 0, k = 0; j < pv[i].size(); j = k) {
      |                                        ~~^~~~~~~~~~~~~~
input/code.cpp:48:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                         while (k < pv[i].size() && pv[i][j] == pv[i][k]) ++k;
      |                                ~~^~~~~~~~~~~~~~
input/code.cpp:49:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                         if ((k - j) * 2 > pv[i].size()) {
      |                             ~~~~~~~~~~~~^~~~~~~~~~~~~~

Code

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

using namespace std;

const int N = 200000;

int v[N], ov[N];
vector<int> occ[N];

const int PN = 1 << 18;
vector<int> pv[PN * 2];
int p[PN * 2];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		ov[i] = v[i];
	}
	sort(ov, ov + n);
	for (int i = 0; i < n; ++i) {
		v[i] = lower_bound(ov, ov + n, v[i]) - ov;
	}

	for (int i = 0; i < n; ++i) {
		occ[v[i]].push_back(i);
	}

	for (int i = 0; i < n; ++i) {
		pv[i + PN] = {v[i]};
		p[i + PN] = v[i];
	}

	for (int i = PN - 1; i >= 1; --i) {
		pv[i].reserve(pv[i * 2].size() + pv[i * 2 + 1].size());
		for (int u : pv[i * 2 + 0]) pv[i].push_back(u);
		for (int u : pv[i * 2 + 1]) pv[i].push_back(u);
		sort(begin(pv[i]), end(pv[i]));
		bool f = 0;
		for (int j = 0, k = 0; j < pv[i].size(); j = k) {
			while (k < pv[i].size() && pv[i][j] == pv[i][k]) ++k;
			if ((k - j) * 2 > pv[i].size()) {
				p[i] = pv[i][j];
				f = 1;
				break;
			}
		}
		if (!f) {
			p[i] = -1;
		}
	}

	while (q--) {
		int ll, rr;
		cin >> ll >> rr;
		ll--;
		rr--;
		int ans = -1;
		auto check = [&](int x) {
			if (x != -1) {
				auto lit = lower_bound(begin(occ[x]), end(occ[x]), ll) - begin(occ[x]);
				auto rit = upper_bound(begin(occ[x]), end(occ[x]), rr) - begin(occ[x]);
				int cnt = rit - lit;
				if (cnt * 2 > rr - ll + 1) {
					ans = ov[x];
				}
			}
		};
		int l = ll + PN, r = rr + PN;
		while (l <= r) {
			if (l % 2 == 1) check(p[l++]);
			if (r % 2 == 0) check(p[r--]);
			l /= 2;
			r /= 2;
		}
		cout << ans << '\n';
	}
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`100 100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`100 100 2 1 2 2 1 2 2 2 1 2 2 1 1 1 1 ...` view save

correct output
`2 1 1 2 1 ...` view save

user output
`2 1 1 2 1 ...` Truncated

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

input
`100 100 5 19 44 88 14 79 50 44 14 99 7...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 1 1 1 2 1 2 1 1 2 1 1 1 1 2 2 ...` view save

correct output
`1 1 2 1 1 ...` view save

user output
`1 1 2 1 1 ...` Truncated

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 8 2 6 1 10 4 9 7 8 10 4 2 8 2 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 7

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 141307 493258596 365539511 222...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 8

Group: 4

Verdict: ACCEPTED

input
`200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 9

Group: 4

Verdict: ACCEPTED

input
`200000 200000 1 2 2 2 1 2 2 1 1 1 1 1 1 1 1 ...` view save

correct output
`2 2 2 2 2 ...` view save

user output
`2 2 2 2 2 ...` Truncated

Test 10

Group: 4

Verdict: ACCEPTED

input
`200000 200000 286470749 280175209 741317063 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` Truncated

Test 11

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 613084013 1000000000 411999902...` view save

correct output
`-1 -1 -1 -1 1000000000 ...` view save

user output
`-1 -1 -1 -1 1000000000 ...` Truncated

Test 12

Group: 4

Verdict: ACCEPTED

input
`200000 200000 613084013 1000000000 411999902...` view save

correct output
`1000000000 1000000000 -1 1000000000 -1 ...` view save

user output
`1000000000 1000000000 -1 1000000000 -1 ...` Truncated

Test 13

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 663307073 663307073 663307073 ...` view save

correct output
`329574367 965067805 768744535 691214891 21873594 ...` view save

user output
`329574367 965067805 768744535 691214891 21873594 ...` Truncated

Test 14

Group: 4

Verdict: ACCEPTED

input
`200000 200000 663307073 663307073 663307073 ...` view save

correct output
`107596959 249558965 679275202 760593154 725418770 ...` view save

user output
`107596959 249558965 679275202 760593154 725418770 ...` Truncated

Test 15

Group: 4

Verdict: ACCEPTED

input
`200000 200000 663307073 663307073 663307073 ...` view save

correct output
`211070558 49212342 651109313 264549124 651109313 ...` view save

user output
`211070558 49212342 651109313 264549124 651109313 ...` Truncated

Test 16

Group: 4

Verdict: ACCEPTED

input
`200000 200000 2 2 2 1 2 1 1 2 2 1 1 1 1 2 1 ...` view save

correct output
`1 2 1 1 1 ...` view save

user output
`1 2 1 1 1 ...` Truncated

Putka Open 2025 – 3/5

Kyselyt

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (hltk)