fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. /*#include<ext/pb_ds/assoc_container.hpp>
  4. #include<ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. /*template <typename T>
  7. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. */typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef long double ld;
  11. typedef pair<ll,ll> pl;
  12. typedef pair<int,int> pii;
  13.  
  14. #define LOCAL 0
  15. #define dbg(x) cout << #x << " is " << x << "\n"
  16. #define gll(x) scanf("%d",&x)
  17. #define gll2(x,y) scanf("%d%d",&x,&y)
  18. #define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  19. #define gllarr(arr,n) f(i,n) gll(arr[i]);
  20. #define sz(x) ((int)x.size())
  21. #define s(x) sort(x.begin(),x.end())
  22. #define all(v) v.begin(),v.end()
  23. #define rs(v) { s(v) ; r(v) ; }
  24. #define r(v) {reverse(all(v));}
  25. #define pb push_back
  26. #define f(i,n) for(int i=0;i<n;i++)
  27. #define fr(i,n) for(int i=n-1;i>=0;i--)
  28. #define rep(i,a,b) for(int i=a;i<=b;i++)
  29. #define repr(i,a,b) for(int i=a;i>=b;i--)
  30.  
  31. const ll mod = (ll)1e9 + 7;
  32. const ll inf = (ll)1e16;
  33. const ld eps = 1e-12;
  34. const ll N = (int)1e4 + 5;
  35. const ll LOGN = 19;
  36. const ld PI = 3.14159265358979323846;
  37. inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  38. inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  39. inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}
  40.  
  41.  
  42. int CountPS(string str, int n)
  43. {
  44.     int dp[n][n];
  45.     memset(dp, 0, sizeof(dp));
  46.     bool P[n][n];
  47.     memset(P, false , sizeof(P));
  48.  
  49.     for (int i= 0; i< n; i++)
  50.         P[i][i] = true;
  51.  
  52.     for (int i=0; i<n-1; i++)
  53.     {
  54.         if (str[i] == str[i+1])
  55.         {
  56.             P[i][i+1] = true;
  57.             dp[i][i+1] = 1 ;
  58.         }
  59.     }
  60.  
  61.     for (int gap=2 ; gap<n; gap++)
  62.     {
  63.         for (int i=0; i<n-gap; i++)
  64.         {
  65.             int j = gap + i;
  66.             if (str[i] == str[j] && P[i+1][j-1] )
  67.                 P[i][j] = true;
  68.  
  69.             if (P[i][j] == true)
  70.                 dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
  71.             else
  72.                 dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
  73.         }
  74.     }
  75.     return dp[0][n-1];
  76. }
  77.  
  78. struct node{
  79.     ll val;
  80.     int index;
  81.     node() {}
  82.     inline void merge(node l, node r)
  83.     {
  84.         if(l.val > r.val)
  85.         {
  86.             val = l.val;
  87.             index = l.index;
  88.         }
  89.         else if(l.val == r.val)
  90.         {
  91.             val = l.val;
  92.             index = min(l.index, r.index);
  93.         }
  94.         else
  95.         {
  96.             val = r.val;
  97.             index = r.index;
  98.         }
  99.     }
  100.  
  101.     inline void no_use()
  102.     {
  103.         val = LONG_LONG_MIN;
  104.         index = -1;
  105.     }
  106. };
  107.  
  108. int num[N];
  109. node segtree[4 * N];
  110.  
  111. void build(int nd, int start, int end)
  112. {
  113.     if(start == end)
  114.     {
  115.         segtree[nd].val = num[start];
  116.         segtree[nd].index = start;
  117.         return;
  118.     }
  119.     int mid = (start + end) >> 1;
  120.     build(2 * nd + 1, start, mid);
  121.     build(2 * nd + 2, mid + 1, end);
  122.     segtree[nd].merge(segtree[2 * nd + 1], segtree[2 * nd + 2]);
  123. }
  124.  
  125. node query(int nd, int start, int end, int qs, int qe)
  126. {
  127.     if(end < qs || start > qe || start > end)
  128.     {
  129.         node temp;
  130.         temp.no_use();
  131.         return temp;
  132.     }
  133.     if(start >= qs && end <= qe) return segtree[nd];
  134.     node p,q;
  135.     int mid = (start + end) >> 1;
  136.     p = query(2 * nd + 1, start, mid, qs, qe);
  137.     q = query(2 * nd + 2, mid + 1, end, qs, qe);
  138.     node ret;
  139.     ret.merge(p,q);
  140.     return ret;
  141. }
  142.  
  143. int main() {
  144.     ios_base::sync_with_stdio(false);
  145.     cin.tie(NULL);
  146.     if (LOCAL) {
  147.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
  148.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
  149.     }
  150.     int t;
  151.     cin>>t;
  152.     while(t--)
  153.     {
  154.         int n,q;
  155.         cin>>n>>q;
  156.         string s;
  157.         unordered_map<string, int> mp;
  158.         f(i,n) {
  159.             cin >> s;
  160.             mp[s] = i;
  161.             int len = s.length();
  162.             num[i] = CountPS(s,len) + len;
  163.         }
  164.         //f(i,n) cout<<num[i]<<" ";
  165.         build(0,0,n-1);
  166.         while(q--)
  167.         {
  168.             string l,r;
  169.             cin>>l>>r;
  170.             int L, R;
  171.             L = mp[l], R = mp[r];
  172.             if(L > R) swap(L,R);
  173.             node ans = query(0, 0, n - 1, L, R);
  174.             cout<<ans.index + 1<<"\n";
  175.         }
  176.     }
  177.     return 0;
  178. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
1
5 5
aaaaa
abaabc
cbbaca
abccba
abca
aaaaa abca
cbbaca abccba
abaabc abccba
abccba abca
abaabc abccba
stdout
copy 
1
4
2
4
2
https://ideone.com/mipoDA
language:
C++ (gcc 8.3)
created:
5 years 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!