Advertisement
sidjha57

segi

Jun 26th, 2022
668
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Siddharth Jha
  2.  
  3. #include<bits/stdc++.h>
  4. //#include<ext/pb_ds/assoc_container.hpp>
  5. //#include<ext/pb_ds/tree_policy.hpp>
  6. //#include <ext/pb_ds/trie_policy.hpp>
  7. //using namespace __gnu_pbds;
  8. using namespace std;
  9. //typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  10. //typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> pbtrie;
  11.  
  12. #define ll                       long long int
  13. #define mod                      1000000007
  14. #define inf                      1e18
  15. #define pb                       push_back
  16. #define vi                       vector<ll>
  17. #define vs                       vector<string>
  18. #define pii                      pair<ll,ll>
  19. #define ump                      unordered_map
  20. #define mp                       make_pair
  21. #define pq_max                   priority_queue<ll>
  22. #define pq_min                   priority_queue<ll,vi,greater<ll> >
  23. #define all(n)                   n.begin(),n.end()
  24. #define ff                       first
  25. #define ss                       second
  26. #define mid(l,r)                 (l+(r-l)/2)
  27. #define bitc(n)                  __builtin_popcount(n)
  28. #define SET(a)                   memset( a, -1, sizeof a )
  29. #define CLR(a)                   memset( a,  0, sizeof a )
  30. #define Pi                       3.141592653589793
  31. #define loop(x,start,end)        for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
  32. #define _fast                    ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  33. #define iter(container,it)       for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  34. #define log(args...)             {string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  35. #define logarr(arr,a,b)          for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
  36. template <typename T> T          gcd(T a, T b){if(a%b) return gcd(b,a%b);return b;}
  37. template <typename T> T          lcm(T a, T b){return (a*(b/gcd(a,b)));}
  38. vs tokenizer(string str,char ch) {std::istringstream var((str)); vs v; string t; while(getline((var), t, (ch))) {v.pb(t);} return v;}
  39.  
  40. void err(istream_iterator<string> it) {}
  41. template<typename T, typename... Args>
  42. void err(istream_iterator<string> it, T a, Args... args) {
  43. cout << *it << " = " << a << endl;
  44. err(++it, args...);
  45. }
  46. class segtree
  47. {
  48. private:
  49.     int n;
  50.     vector<int> segtree;
  51. public:
  52.     void init(int n)
  53.     {
  54.         this->n = n;
  55.         segtree.resize(4 * n + 1);
  56.     }
  57.     int op(int x, int y)
  58.     {
  59.         return (x + y);
  60.     }
  61.     void updateVal(int x, int l, int r, int idx, int val)
  62.     {
  63.         if (l > idx or r < idx)
  64.             return;
  65.         if (l == r)
  66.         {
  67.             segtree[x] += val;
  68.             return;
  69.         }
  70.         int mid = (l + r) / 2LL;
  71.         updateVal(2 * x, l, mid, idx, val);
  72.         updateVal(2 * x + 1, mid + 1, r, idx, val);
  73.         segtree[x] = op(segtree[2 * x], segtree[2 * x + 1]);
  74.     }
  75.     void set(int idx, int val)
  76.     {
  77.         updateVal(1, 1, n, idx, val);
  78.     }
  79.     int cal(int x, int l, int r, int L, int R)
  80.     {
  81.         if (L <= l and R >= r)
  82.             return segtree[x];
  83.         if (L > r or R < l)
  84.             return 0;
  85.         int mid = (l + r) / 2LL;
  86.         return op(cal(2 * x, l, mid, L, R), cal(2 * x + 1, mid + 1, r, L, R));
  87.     }
  88.     int sum(int l, int r)
  89.     {
  90.         return l > r ? 0 : cal(1, 1, n, l, r);
  91.     }
  92. };
  93.  
  94. void solve() {
  95.    
  96.    int n,q;
  97.    cin >> n >> q;
  98.    string s ;
  99.    cin >> s;
  100.    vector<int> arr (n);
  101.    loop (i,0,n) cin >> arr[i];
  102.    vector<vector<int>> ranges (q, vector<int>(2));
  103.    loop (i,0,q) cin >> ranges[i][0] >> ranges[i][1];
  104.  
  105.    set<pair<int,int>> range;
  106.    for (int i = 0; i < q; i++) {
  107.     range.insert({ranges[i][0],ranges[i][1]});
  108.    }
  109.    
  110.    segtree seg[26];
  111.    vector<vector<int>> freq (26, vector<int>(n,0));
  112.  
  113.    for (int i = 0; i < n; i++) {
  114.     int idx = (s[i] - 'a');
  115.     freq[idx][i]++;
  116.    }
  117.    for (int i = 0; i < 26; i++) {
  118.     seg[i].init(n);
  119.     for (int j = 0; j < n; j++){
  120.         seg[i].set(j+1,freq[i][j]);
  121.     }
  122.    
  123.    }
  124.     bool flag = 1;
  125.     for (int c = 0; c < 26; c++) {
  126.          for (auto r : range) {
  127.             if (seg[c].sum(r.first, r.second) > 1) {
  128.                 flag = 0;
  129.                 break;
  130.             }
  131.         }
  132.         if (!flag) break;
  133.     }
  134.     if (flag) {
  135.         cout << 0;
  136.         return;
  137.     }
  138.    for (int i=0; i<n; i++) {
  139.  
  140.         int idx = (s[arr[i]] - 'a'), v = -1, id = arr[i];
  141.         seg[idx].set(id,v);
  142.         flag = 1;
  143.         for (int c = 0; c < 26; c++) {
  144.              for (auto r : range) {
  145.                 if (seg[c].sum(r.first, r.second) > 1) {
  146.                     flag = 0;
  147.                     break;
  148.                 }
  149.              }
  150.              if (!flag) break;
  151.         }
  152.         if (flag) {
  153.             cout << i+1;
  154.             return;
  155.         }
  156.    }
  157. }
  158.  
  159. int main(int argc, char const *argv[]){
  160.     _fast
  161.   //#ifndef ONLINE_JUDGE
  162.         //freopen("input.txt", "r", stdin);
  163.         //freopen("output.txt", "w", stdout);
  164.   //#endif
  165.     ll t; cin>>t;
  166.     while(t--){
  167.      solve();
  168.     }
  169.   return 0;
  170. }
Advertisement
RAW Paste Data Copied
Advertisement