Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Siddharth Jha
- #include<bits/stdc++.h>
- //#include<ext/pb_ds/assoc_container.hpp>
- //#include<ext/pb_ds/tree_policy.hpp>
- //#include <ext/pb_ds/trie_policy.hpp>
- //using namespace __gnu_pbds;
- using namespace std;
- //typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
- //typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> pbtrie;
- #define ll long long int
- #define mod 1000000007
- #define inf 1e18
- #define pb push_back
- #define vi vector<ll>
- #define vs vector<string>
- #define pii pair<ll,ll>
- #define ump unordered_map
- #define mp make_pair
- #define pq_max priority_queue<ll>
- #define pq_min priority_queue<ll,vi,greater<ll> >
- #define all(n) n.begin(),n.end()
- #define ff first
- #define ss second
- #define mid(l,r) (l+(r-l)/2)
- #define bitc(n) __builtin_popcount(n)
- #define SET(a) memset( a, -1, sizeof a )
- #define CLR(a) memset( a, 0, sizeof a )
- #define Pi 3.141592653589793
- #define loop(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
- #define _fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #define iter(container,it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
- #define log(args...) {string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
- #define logarr(arr,a,b) for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
- template <typename T> T gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
- template <typename T> T lcm(T a, T b){return (a*(b/gcd(a,b)));}
- vs tokenizer(string str,char ch) {std::istringstream var((str)); vs v; string t; while(getline((var), t, (ch))) {v.pb(t);} return v;}
- void err(istream_iterator<string> it) {}
- template<typename T, typename... Args>
- void err(istream_iterator<string> it, T a, Args... args) {
- cout << *it << " = " << a << endl;
- err(++it, args...);
- }
- class segtree
- {
- private:
- int n;
- vector<int> segtree;
- public:
- void init(int n)
- {
- this->n = n;
- segtree.resize(4 * n + 1);
- }
- int op(int x, int y)
- {
- return (x + y);
- }
- void updateVal(int x, int l, int r, int idx, int val)
- {
- if (l > idx or r < idx)
- return;
- if (l == r)
- {
- segtree[x] += val;
- return;
- }
- int mid = (l + r) / 2LL;
- updateVal(2 * x, l, mid, idx, val);
- updateVal(2 * x + 1, mid + 1, r, idx, val);
- segtree[x] = op(segtree[2 * x], segtree[2 * x + 1]);
- }
- void set(int idx, int val)
- {
- updateVal(1, 1, n, idx, val);
- }
- int cal(int x, int l, int r, int L, int R)
- {
- if (L <= l and R >= r)
- return segtree[x];
- if (L > r or R < l)
- return 0;
- int mid = (l + r) / 2LL;
- return op(cal(2 * x, l, mid, L, R), cal(2 * x + 1, mid + 1, r, L, R));
- }
- int sum(int l, int r)
- {
- return l > r ? 0 : cal(1, 1, n, l, r);
- }
- };
- void solve() {
- int n,q;
- cin >> n >> q;
- string s ;
- cin >> s;
- vector<int> arr (n);
- loop (i,0,n) cin >> arr[i];
- vector<vector<int>> ranges (q, vector<int>(2));
- loop (i,0,q) cin >> ranges[i][0] >> ranges[i][1];
- set<pair<int,int>> range;
- for (int i = 0; i < q; i++) {
- range.insert({ranges[i][0],ranges[i][1]});
- }
- segtree seg[26];
- vector<vector<int>> freq (26, vector<int>(n,0));
- for (int i = 0; i < n; i++) {
- int idx = (s[i] - 'a');
- freq[idx][i]++;
- }
- for (int i = 0; i < 26; i++) {
- seg[i].init(n);
- for (int j = 0; j < n; j++){
- seg[i].set(j+1,freq[i][j]);
- }
- }
- bool flag = 1;
- for (int c = 0; c < 26; c++) {
- for (auto r : range) {
- if (seg[c].sum(r.first, r.second) > 1) {
- flag = 0;
- break;
- }
- }
- if (!flag) break;
- }
- if (flag) {
- cout << 0;
- return;
- }
- for (int i=0; i<n; i++) {
- int idx = (s[arr[i]] - 'a'), v = -1, id = arr[i];
- seg[idx].set(id,v);
- flag = 1;
- for (int c = 0; c < 26; c++) {
- for (auto r : range) {
- if (seg[c].sum(r.first, r.second) > 1) {
- flag = 0;
- break;
- }
- }
- if (!flag) break;
- }
- if (flag) {
- cout << i+1;
- return;
- }
- }
- }
- int main(int argc, char const *argv[]){
- _fast
- //#ifndef ONLINE_JUDGE
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- //#endif
- ll t; cin>>t;
- while(t--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement