DCP-119: Hard Task Back to All Problems

Medium Data Structures > Orthogonal Range Search

**IIT (DU)** has started it's journey just a few years ago. Although we are dedicated for software development, some of us are very interested in competitive programming. As a student of 3rd year, yesterday I took a class on Longest Common Subsequence for 1st year students. As you know the algorithm of finding the length of LCS has a high complexity one of them asked me if it is impossible to find the length of LCS of two arrays both of length 100000. I thought a little bit and answered that it is only possible if both the arrays only contain distinct elements. Now I set the same task for you. Input: ------ First line of input consists of two integers **N (1 <= N <= 100000)** and **M (1 <= M <= 100000)** separated by a space. Second line of input contains **N** distinct integers representing the first array. Third line of input contains **M** distinct integers representing the second array. Each number of both array is in range **[1, 1000000]**. Output: ------- You just need to print the length of LCS. Sample Input ------------ 5 5 1 2 3 4 5 2 3 4 5 1 Sample Output ------------- 4

Problem Setter:

Feroz Ahmmed

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats




# User Language Timing
01 anik_JU Cpp 0.03s
02 feodorv C 0.04s
03 Robbinb1993 Cpp14 0.04s
04 rayhan50001 Cpp14 0.05s
05 humayan7711 Cpp14 0.11s
06 Tahmid Cpp14 0.11s
07 seyedssz Cpp14 0.13s
08 Morass Cpp14 0.14s
09 tariqiitju Cpp 0.18s
10 anowar1112 Cpp14 0.33s
11 abinash Cpp14 0.34s
12 murad_al_wajed Cpp 0.36s
13 adamantium Cpp14 0.39s
14 ksohan Cpp14 0.41s
15 BishalG Cpp14 0.43s
16 sahedsohel Cpp14 0.43s
17 raihanruhin Cpp14 0.43s
18 alhelal_cse Cpp14 0.43s
19 jahid_ict Cpp14 0.43s
20 Fahim_Ahmed Cpp14 0.44s
21 udashi Cpp14 0.46s
22 ahqmrf Cpp14 0.47s
23 shaheen_bd Cpp14 0.48s
24 khatribiru Cpp14 0.49s
25 Mahmudul_Tushar Cpp14 0.51s
26 Digonta Cpp14 0.53s
27 akazad_cse13_ruet Cpp14 0.57s
28 mamun4122 Cpp14 0.57s
29 amin21 Cpp14 0.58s
30 Double_O Cpp14 0.62s
31 jayanto Cpp14 0.62s
32 bhadra Cpp14 0.64s
33 sohag_hstu Cpp14 0.72s
34 froghramar Cpp14 0.86s
35 roxter Java 2.32s

Your feedback is our precious!

Or call +88 02 9853138 for support