#include <bits/stdc++.h>
#define endl "\n"
#define fast() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
using namespace std;
int N,Q;
string s;
struct STmx{
int len = 1;
vector<pair<ll,ll>> tree;
STmx(int l){
while(len < l){
len *= 2;
}
tree = vector<pair<ll,ll>>(len*2,{-1e9,-1e9});
}
pair<ll,ll> takeBest(pair<ll,ll> a,pair<ll,ll> b){
/*if(a.first<a.second)
swap(a.first,a.second);
if(b.first<b.second)
swap(b.first,b.second);
if(a.second<b.first)
swap(a.second,b.first);
if(a.first<a.second)
swap(a.first,a.second);
if(b.first<b.second)
swap(b.first,b.second);
if(a.second<b.first)
swap(a.second,b.first);
if(a.first<a.second)
swap(a.first,a.second);*/
set<ll> s;
s.insert(a.first);
s.insert(a.second);
s.insert(b.first);
s.insert(a.second);
vector<ll> v;
for(auto x : s)
v.push_back(x);
sort(v.rbegin(),v.rend());
return make_pair(v[0],v[1]);
}
void insert(int idx,int val){
idx += len;
tree[idx] = {val,-1e9};
for(idx/=2;idx>=1;idx/=2){
/*vector<ll> cur = {tree[idx*2].first,tree[idx*2].second,
tree[idx*2+1].first,tree[idx*2+1].second};
sort(cur.rbegin(),cur.rend());*/
tree[idx] = takeBest(tree[idx*2],tree[idx*2+1]);
}
}
pair<ll,ll> get(int l,int r){
l += len,r += len;
pair<ll,ll> mx = tree[l];
while(l<=r){
if(l%2==1){
mx = takeBest(mx,tree[l++]);
}
if(r%2==0){
mx = takeBest(mx,tree[r--]);
}
l/=2,r/=2;
}
return mx;
}
};
void solve(){
cin >> s;
N = s.size();
cin >> Q;
vector<pair<int,int>> query;
for(int i=0;i<Q;i++){
int l,r;
cin >> l >> r;
l--,r--;
query.pb(make_pair(l,r));
}
vector<int> p(N);
for(int i=0;i<N;i++){
int pos;
cin >> pos;
pos--;
p[pos] = i+1;
}
vector<STmx> segs;
for(int c=0;c<26;c++){
STmx seg(N);
for(int i=0;i<N;i++){
if((s[i]-'a')==c){
seg.insert(i,p[i]);
}
}
segs.push_back(seg);
}
ll ans = 0;
for(int i=0;i<Q;i++){
int l=query[i].first,r=query[i].second;
//cout << "lr :" << l<< ' ' << r << endl;
for(int c=0;c<26;c++){
//cout << c << ' ' << segs[c].get(l,r).first << ' ' << segs[c].get(l,r).second << endl;;
ans = max(ans,segs[c].get(l,r).second);
}
}
cout << ans << endl;
//cout << segs[1].get(0,2).first << ' ' << segs[1].get(0,2).second << endl;
}
int main(){
fast()
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
# | 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... |