Submission #222371

#	Time	Username	Problem	Language	Result	Execution time	Memory
222371		oolimry	Grudanje (COCI19_grudanje)	C++14	70 / 70	257 ms	12536 KiB

grudanje

#include <bits/stdc++.h>

using namespace std;

int arr[100005];
int pre[26][100005];
int cnt[26][100005];
int badcnt[100005];
int L[100005];
int R[100005];
int p[100005];
bool isSnow[100005];
int n; int Q; 

bool solve(int take){
	
	fill(isSnow, isSnow + (n+1), false);
	
	for(int i = 0;i <= take;i++) isSnow[p[i]] = true;
	
	for(int i = 1;i <= n;i++){
		int c = arr[i];
		
		for(int j = 0;j < 26;j++){
			pre[j][i] = pre[j][i-1];
			if(j == (c) && !isSnow[i]) pre[j][i]++;
		}
	}
	
	//cout << take << ": \n";
	for(int i = 0;i < Q;i++){
		int l = L[i], r = R[i];
		
		for(int c = 0;c < 26;c++){
			
			if(pre[c][r] - pre[c][l-1] >= 2){
				return false;
			}				
		}
	}
	return true;
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	string s; cin >> s;
	n = s.length();
	
	for(int i = 0;i < n;i++){
		arr[i+1] = s[i] - 'a';
	}
	
	
	
	
	
	cin >> Q;
	
	for(int i = 0;i < Q;i++){
		int l, r; cin >> l >> r;
		L[i] = l; R[i] = r;
		//cout << l << " "  << r << "\n";
	}
	
	for(int i = 0;i < n;i++) cin >> p[i];
	
	int low = -2; int high = n;
	while(true){
		if(low == high - 1) break;
		int mid = (low + high) / 2;
		
		if(solve(mid)) high = mid;
		else low = mid;
	}
	
	cout << high + 1;
}

• 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