Submission #291912

#	Time	Username	Problem	Language	Result	Execution time	Memory
291912		penguinhacker	Grudanje (COCI19_grudanje)	C++17	70 / 70	177 ms	13920 KiB

grudanje

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, p[mxN], ps[mxN+1][26];
string s;
ar<int, 2> qry[mxN];

bool ok(int x) {
	memset(ps, 0, sizeof(ps));
	string cur=s;
	for (int i=0; i<x; ++i) cur[p[i]]='#';
	for (int i=0; i<n; ++i) {
		for (int j=0; j<26; ++j) ps[i+1][j]=ps[i][j];
		if (cur[i]!='#') ps[i+1][cur[i]-'a']++;
	}
	for (int i=0; i<q; ++i) {
		int a=qry[i][0], b=qry[i][1];
		for (int j=0; j<26; ++j) if (ps[b][j]-ps[a][j]>1) return 0;
	}
	return 1;
}

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

	cin >> s >> q, n=s.size();
	for (int i=0; i<q; ++i) {
		int a, b; cin >> a >> b, --a;
		qry[i]={a, b};
	}
	for (int i=0; i<n; ++i) cin >> p[i], --p[i];
	int l=0, r=n;
	while(l<r) {
		int mid=(l+r)/2;
		if (ok(mid)) r=mid;
		else l=mid+1;
	}
	cout << l << "\n";
	return 0;
}

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