This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
string str, cur;
int n, q, balls[N];
array<int, 26> prefix[N];
pair<int, int> query[N];
bool check(int m){
cur = str;
for(int i = 1; i <= m; i++) cur[balls[i]] = '.';
for(int i = 1; i <= n; i++){
prefix[i] = prefix[i - 1];
if(cur[i] != '.') prefix[i][cur[i] - 'a']++;
}
for(int i = 0; i < q; i++){
for(int j = 0; j < 26; j++){
if(prefix[query[i].second][j] - prefix[query[i].first - 1][j] > 1) return false;
}
}
return true;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin >> str;
n = str.size();
str = '$' + str;
cin >> q;
for(int i = 0; i < q; i++) cin >> query[i].first >> query[i].second;
for(int i = 1; i <= n; i++) cin >> balls[i];
int l = -1, r = n, m;
while(r - l > 1){
m = l + (r - l) / 2;
if(check(m)) r = m;
else l = m;
}
cout << r;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |