Submission #1276850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276850		zyb_txdy	Lollipop (POI11_liz)	C++17	100 / 100	236 ms	27316 KiB

liz

#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)

using namespace std;

constexpr int N = 1e6 + 5;

int n, m, sum, pos;
int a[N], suf[N], buc[N << 1];
char s[N];

void Solve() {
	int x;
	cin >> x;
	
	if (x > sum) {
		cout << "NIE\n";
		return;
	} else if (~buc[x]) {
		cout << "1 " << buc[x] << '\n';
		return;
	} else if (x == 1) {
		if (pos) {
			cout << pos << ' ' << pos << '\n';
		} else {
			cout << "NIE\n";
		}
		return;
	}
	
	int p = buc[x - 1];
	assert(p > 0);
	if (suf[1] < suf[p + 1]) {
		cout << suf[1] + 2 << ' ' << p + suf[1] + 1 << '\n';
	} else if (suf[1] >= suf[p + 1] && p + suf[p + 1] < n) {
		cout << suf[p + 1] + 1 << ' ' << p + suf[p + 1] + 1 << '\n';
	} else {
		cout << "NIE\n";
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n >> m >> s + 1;
	for (int i = 1; i <= n; ++i) {
		a[i] = 1 + (s[i] == 'T');
	}
	
	for (int i = n; i > 0; --i) {
		if (a[i] == 2) {
			suf[i] = suf[i + 1] + 1;
		}
	}
	fill(buc, buc + 2 * n + 1, -1);
	for (int i = 1; i <= n; ++i) {
		sum += a[i];
		buc[sum] = i;
		if (a[i] == 1) {
			pos = i;
		}
	}
	
	while (m--) {
		Solve();
	}
	
	return 0;
}
/*
感觉前几篇题解都不是人类了，来点是人类能想到的做法
首先这个值域是 2，容易感受到前缀和必定非常的密集。一个具象的推论是：“和为 x 的前缀”和“和为 x - 1 的前缀”必定至少存在一个。
显然只需考虑只有后者存在的情况。
设这段前缀是 [1, p]，发现找到 a[1] 和 a[p] 后面的第一个 1 并加上 O(1) 的讨论就做完了。找后面的第一个 1 也显然容易预处理。
做法的正确性不难证明，时间复杂度为 $O(n + m)$。 
判掉 x > sum 和 x = 1 的 corner case。
*/

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9