fork download
copy 
  1. import java.util.*;
  2. import java.io.*; 
  3. import java.text.*;
  4. //Solution Credits: Taranpreet Singh
  5. public class Main{
  6.     //SOLUTION BEGIN
  7.     int n, q, m = 1, cnt, MX = (int)1e6+1;
  8.     String[] a;
  9.     Integer[] b;
  10.     int[] root;
  11.     int[] t, le, ri;
  12.     int[] maxPref, tt;
  13.     int[][] bit;
  14.     String x;
  15.     void solve(int TC) throws Exception{
  16.         n  = ni(); q = ni();
  17.         a = new String[n+1];b = new Integer[1+n];b[0] = 0;a[0] = "";
  18.         int[] count = new int[MX];
  19.         for(int i = 1; i<= n; i++){
  20.             a[i] = n();b[i] = i;
  21.         }
  22.  
  23.         Arrays.sort(b, 1, n+1, (Integer i1, Integer i2) ->{
  24.             if(a[i1].length()!=a[i2].length())return Integer.compare(a[i1].length(), a[i2].length());
  25.             return a[i1].compareTo(a[i2]);
  26.         });
  27.         for(int i = 1; i<= n; i++)
  28.             for(int j = 0; j< a[b[i]].length(); j++)
  29.                 if(a[b[i]].charAt(j)=='1')
  30.                     count[a[b[i]].length()-j-1]++;
  31.         bit = new int[MX][];
  32.         for(int i = 0; i< MX; i++){bit[i] = new int[count[i]];count[i] = 0;}
  33.         for(int i = 1; i<= n; i++)
  34.             for(int j= 0; j< a[b[i]].length(); j++)
  35.                 if(a[b[i]].charAt(j)=='1')
  36.                     bit[a[b[i]].length()-j-1][count[a[b[i]].length()-j-1]++] = i;
  37.         buildt();
  38.         buildtt();
  39.         while(q-->0){
  40.             int l = ni(), r = ni();
  41.             x = new StringBuilder(n()).reverse().toString();
  42.             int ll = 1, rr = n, len = x.length();
  43.             while(ll<rr-1){
  44.                 int mid = (ll+rr)>>1;
  45.                 if(a[b[mid]].length()>len)rr = mid;
  46.                 else ll = mid;
  47.             }
  48.             if(a[b[ll]].length()>len)rr=ll;
  49.             if(a[b[rr]].length()<=len || !check(rr, n, l,r)){
  50.                 if(a[b[rr]].length()>len)rr--;
  51.                 pn(solve(1,rr,l,r,len-1));
  52.             }else{
  53.                 int z = get_last_pos(1,m,root[l],r);
  54.                 int zz = get_pos_second(1,m,1,z,1,a[b[z]].length()-len);
  55.                 pn(solve(zz,z,l,r,len-1));
  56.             }
  57.         }
  58.     }
  59.     void buildt(){
  60.         while(m<n)m<<=1;
  61.         cnt = 1+(m<<1);
  62.         t = new int[MX*6];le = new int[MX*6];ri = new int[MX*6];
  63.         root = new int[n+2];root[n+1] = 1;
  64.         for(int i = 1; i< m; i++){le[i] = i<<1;ri[i] = i<<1|1;}
  65.         for(int i = 1; i<= m<<1; i++)t[i] = INF;
  66.         int[] pos = new int[n+1];
  67.         for(int i = 1; i<= n; i++)pos[b[i]] = i;
  68.         for(int i = n; i>=1; i--){
  69.             root[i] = createCopy(root[i+1]);
  70.             update(1, m, pos[i], root[i], i);
  71.         }
  72.     }
  73.     void update(int l, int r, int pos, int node, int z){
  74.         if(l==r)t[node] = z;
  75.         else{
  76.             int mid = (l+r)/2;
  77.             if(pos<=mid){
  78.                 le[node] = createCopy(le[node]);
  79.                 update(l, mid, pos, le[node], z);
  80.             }else{
  81.                 ri[node] = createCopy(ri[node]);
  82.                 update(mid+1,r,pos,ri[node], z);
  83.             }
  84.             t[node] = Math.min(t[le[node]], t[ri[node]]);
  85.         }
  86.     }
  87.  
  88.     int get(int l, int r, int ll, int rr, int node){
  89.         if(l==ll && r==rr)return t[node];
  90.         int mid = (ll+rr)/2;
  91.         if(r<=mid)return get(l,r,ll,mid,le[node]);
  92.         else if(l>mid)return get(l,r,mid+1,rr,ri[node]);
  93.         else return Math.min(get(l,mid,ll,mid,le[node]), get(mid+1,r,mid+1,rr,ri[node]));
  94.     }
  95.  
  96.     boolean check(int l, int r, int ll, int rr){
  97.         return get(l,r,1,m,root[ll])<=rr;
  98.     }
  99.  
  100.     int get_last_pos(int l, int r, int node, int rr){
  101.         if(l==r)return l;
  102.         int mid = (l+r)/2;
  103.         if(t[ri[node]]<=rr)return get_last_pos(mid+1,r,ri[node],rr);
  104.         return get_last_pos(l,mid,le[node], rr);
  105.     }
  106.  
  107.     int get_pos(int l, int r, int x){
  108.         if(bit[x].length==0)return r+1;
  109.         int ll = 0, rr = bit[x].length-1;
  110.         while(ll<rr-1){
  111.             int mid = (ll+rr)>>1;
  112.             if(bit[x][mid]>=l)rr=mid;
  113.             else ll = mid;
  114.         }
  115.         if(bit[x][ll]>=l)rr=ll;
  116.         if(bit[x][rr]<l)return r+1;
  117.         return bit[x][rr];
  118.     }
  119.     int solve(int l, int r, int ll, int rr, int bit){
  120.         if(bit==-1)return get(l,r,1,m,root[ll]);
  121.         int pos = get_pos(l,r,bit);
  122.         pos = Math.min(pos, r+1);
  123.         if(x.charAt(bit)=='1'){
  124.             if(pos>l && check(l,pos-1, ll,rr))return solve(l,pos-1,ll,rr,bit-1);
  125.             else return solve(pos, r, ll, rr, bit-1);
  126.         }else{
  127.             if(pos<=r && check(pos,r,ll,rr))return solve(pos,r,ll,rr,bit-1);
  128.             else return solve(l,pos-1,ll,rr,bit-1);
  129.         }
  130.     }
  131.     int get_pos_second(int l, int r, int ll, int rr, int i, int y){
  132.         if (l>r || ll>r || l>rr || ll>rr) return 0;
  133.         if(l>=ll && r<=rr && tt[i]>=y)return 0;
  134.         if(l==r)return l;
  135.         int mid = (l+r)/2;
  136.         int x = get_pos_second(mid+1,r,ll,rr,i<<1|1, y);
  137.         if(x>0)return x;
  138.         return get_pos_second(l,mid,ll,rr,i<<1,y);
  139.     }
  140.     void buildtt(){
  141.         maxPref = new int[m<<1];
  142.         for(int i = 1; i<= n; i++){
  143.             int x = b[i-1], y = b[i];
  144.             if(a[x].length()==a[y].length())while(maxPref[i]<a[x].length() && a[x].charAt(maxPref[i]) == a[y].charAt(maxPref[i]))maxPref[i]++;
  145.         }
  146.         tt = new int[m<<1];
  147.         for(int i = 1; i< m<<1; i++)tt[i] = INF;
  148.         for(int i = m; i< m+n; i++)tt[i] = maxPref[i-m+1];
  149.         for(int i = m-1; i>0; i--)tt[i] = Math.min(tt[i<<1], tt[i<<1|1]);
  150.     }
  151.     int createCopy(int x){
  152.         t[cnt] = t[x];
  153.         le[cnt] = le[x];
  154.         ri[cnt] = ri[x];
  155.         return cnt++;
  156.     }
  157.     //SOLUTION END
  158.     long mod = (long)1e9+7, IINF = (long)5e18;
  159.     final int INF = (int)2e9;
  160.     DecimalFormat df = new DecimalFormat("0.000000000");
  161.     double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
  162.     static boolean multipleTC = false, memory = false;
  163.     FastReader in;PrintWriter out;
  164.     void run() throws Exception{
  165.         in = new FastReader();
  166.         out = new PrintWriter(System.out);
  167.         int T = (multipleTC)?ni():1;
  168.         //Solution Credits: Taranpreet Singh
  169.         for(int i = 1; i<= T; i++)solve(i);
  170.         out.flush();
  171.         out.close();
  172.     }
  173.     public static void main(String[] args) throws Exception{
  174.         if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
  175.         else new Main().run();
  176.     }
  177.     long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
  178.     int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
  179.     int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
  180.     void p(Object o){out.print(o);}
  181.     void pn(Object o){out.println(o);}
  182.     void pni(Object o){out.println(o);out.flush();}
  183.     String n(){return in.next();}
  184.     String nln(){return in.nextLine();}
  185.     int ni(){return Integer.parseInt(in.next());}
  186.     long nl(){return Long.parseLong(in.next());}
  187.     double nd(){return Double.parseDouble(in.next());}
  188.  
  189.     class FastReader{
  190.         BufferedReader br;
  191.         StringTokenizer st;
  192.         public FastReader(){
  193.             br = new BufferedReader(new InputStreamReader(System.in));
  194.         }
  195.  
  196.         public FastReader(String s) throws Exception{
  197.             br = new BufferedReader(new FileReader(s));
  198.         }
  199.  
  200.         String next(){
  201.             while (st == null || !st.hasMoreElements()){
  202.                 try{
  203.                     st = new StringTokenizer(br.readLine());
  204.                 }catch (IOException  e){
  205.                     e.printStackTrace();
  206.                 }
  207.             }
  208.             return st.nextToken();
  209.         }
  210.  
  211.         String nextLine(){
  212.             String str = "";
  213.             try{    
  214.                 str = br.readLine();
  215.             }catch (IOException e){
  216.                 e.printStackTrace();
  217.             }   
  218.             return str;
  219.         }
  220.     }
  221. }
Success #stdin #stdout 0.25s 2184192KB
comments (?)
stdin
copy 
5 4
100
101
1
1011
11
2 3 10
1 5 1100
3 5 1010
1 5 11100
stdout
copy 
2
5
3
5
https://ideone.com/dyc1Pq
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

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!