fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define FOR(i,l,r) for(int i = l; i<= r; i++)
  5. #define fastIO ios::sync_with_stdio(0);cout.tie(0);cin.tie(0)
  6. #define FORD(i,r,l) for(int i = r; i >=l ; i--)
  7. #define LINF 0x3f3f3f3f3f3f3f3f
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define pii pair<int,int>
  12. string s;
  13. int q;
  14. int n;
  15. int cnt[30][200005];
  16. vector<pii> qr;
  17. int a[100005];
  18. void read(){
  19. cin>>s>>q;
  20. FOR(i,1,q){
  21.      int a,b;
  22.      cin>>a>>b;
  23.      qr.pb({a,b});
  24.   }
  25.   FOR(i,1,s.size()){
  26.      cin>>a[i];
  27.   }
  28.    n = s.size();
  29.   s = ' ' + s;
  30.   FOR(i,1,n){
  31.      FOR(j,0,26) cnt[j][i] = cnt[j][i-1];
  32.      cnt[s[i]-'a'][i] ++;
  33.   }
  34. }
  35. bool check(int k){
  36.   int dem[30][200005];
  37. FOR(c,0,25){
  38.     FOR(i,0,n){
  39.         dem[c][i] = cnt[c][i];
  40.     }
  41. }
  42.    FOR(i,1,k){
  43.       dem[s[a[i]]-'a'][a[i]]--;
  44.    }
  45.    FOR(i,1,q){
  46.       int l = qr[i].fi;
  47.       int r = qr[i].se;
  48.       FOR(c,0,26){
  49.            if(dem[c][r] - dem[c][l-1] > 1) return false;
  50.        }
  51.    }
  52.    return true;
  53. }
  54. void solve(){
  55.    int l = 1;
  56.    int r = s.size();
  57.    int ans = 0;
  58.    while(l <= r){
  59.     int mid = (r+l)/2;
  60.     if(check(mid)){
  61.         r= mid -1;
  62.         ans = mid;
  63.     }
  64.     else{
  65.         l = mid + 1;
  66.     }
  67.    }
  68.    cout<<ans;
  69. }
  70. int main(){
  71. fastIO;
  72. read();
  73. solve();
  74. }
  75.  
Success #stdin #stdout 0.01s 24000KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/uFwPt7
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!