{"id":"d182b66f-b961-44c3-a120-107522edf58d","name":"Moksh And His Girlfriend","description":"Recently Moksh(HR of Pepcoding) invented a serum which can increase height of plant by 1 unit. Moksh's girlfriend birthday is next month.\r\nHe is planning something amazing as a gift for her.His girlfriend's favourite Integer is M.\r\n\r\nInitially Moksh has N (1 to N) no. of beautiful Rose plants, Each plant can have an Integer height,Initially the height of each plant is zero.\r\nSubhesh gives Moksh Q number of operations,In each operation Moksh got two integer start and end and he increases the height of all the plants between start and end position (including start and end) by 1.\r\nAs Moksh wasn't happy with the pattern of height of the plants formed, He went to Rajneesh and asked him to remove any 1 operation from the Q operations such that the count of plants with height M is maximum possible.\r\nOutput the maximum possible number of plants with height M.\r\n\r\nExpected Complexity : O(n+q)","inputFormat":"First line contains three space separated integer N(no. of Rose plants), Q(number of operations), M.\r\nEach of the next Q lines contains two space-separated integers L and R describing one operation.","outputFormat":"print a single line containing one integer - the maximum possible number of Trees with height M.","constraints":"Constraint : \r\n2<=N<=100000.\r\n2<=Q<=100000.\r\n1<=M<Q.\r\n1<=L<=R<=N.","sampleCode":{"cpp":{"code":" #include using namespace std;\r\n int main(){ }"},"java":{"code":"import java.io.*;\r\n import java.util.*;\r\n public class main {\r\n public static void main(String[] args) {\r\n }\r\n }\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"10 3 2\r\n2 6\r\n4 9\r\n1 4","sampleOutput":"3","questionVideo":"https://www.youtube.com/embed/f43qOr8eTlU","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"708eaf40-ad8a-4b4f-b9f6-8c4276e08d11","name":"Moksh And His Girlfriend","slug":"moksh-and-his-girlfriend","type":1}],"next":{"id":"8df650ba-ffc6-4622-b357-34779040e18e","name":"Square Root Decomposition","type":1,"slug":"square-root-decomposition"},"prev":{"id":"2684424c-b1dd-4289-b0a2-3ade526b3874","name":"Range Addition","type":1,"slug":"range-addition"}}}

Moksh And His Girlfriend

Recently Moksh(HR of Pepcoding) invented a serum which can increase height of plant by 1 unit. Moksh's girlfriend birthday is next month. He is planning something amazing as a gift for her.His girlfriend's favourite Integer is M. Initially Moksh has N (1 to N) no. of beautiful Rose plants, Each plant can have an Integer height,Initially the height of each plant is zero. Subhesh gives Moksh Q number of operations,In each operation Moksh got two integer start and end and he increases the height of all the plants between start and end position (including start and end) by 1. As Moksh wasn't happy with the pattern of height of the plants formed, He went to Rajneesh and asked him to remove any 1 operation from the Q operations such that the count of plants with height M is maximum possible. Output the maximum possible number of plants with height M. Expected Complexity : O(n+q)

{"id":"d182b66f-b961-44c3-a120-107522edf58d","name":"Moksh And His Girlfriend","description":"Recently Moksh(HR of Pepcoding) invented a serum which can increase height of plant by 1 unit. Moksh's girlfriend birthday is next month.\r\nHe is planning something amazing as a gift for her.His girlfriend's favourite Integer is M.\r\n\r\nInitially Moksh has N (1 to N) no. of beautiful Rose plants, Each plant can have an Integer height,Initially the height of each plant is zero.\r\nSubhesh gives Moksh Q number of operations,In each operation Moksh got two integer start and end and he increases the height of all the plants between start and end position (including start and end) by 1.\r\nAs Moksh wasn't happy with the pattern of height of the plants formed, He went to Rajneesh and asked him to remove any 1 operation from the Q operations such that the count of plants with height M is maximum possible.\r\nOutput the maximum possible number of plants with height M.\r\n\r\nExpected Complexity : O(n+q)","inputFormat":"First line contains three space separated integer N(no. of Rose plants), Q(number of operations), M.\r\nEach of the next Q lines contains two space-separated integers L and R describing one operation.","outputFormat":"print a single line containing one integer - the maximum possible number of Trees with height M.","constraints":"Constraint : \r\n2<=N<=100000.\r\n2<=Q<=100000.\r\n1<=M<Q.\r\n1<=L<=R<=N.","sampleCode":{"cpp":{"code":" #include using namespace std;\r\n int main(){ }"},"java":{"code":"import java.io.*;\r\n import java.util.*;\r\n public class main {\r\n public static void main(String[] args) {\r\n }\r\n }\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"10 3 2\r\n2 6\r\n4 9\r\n1 4","sampleOutput":"3","questionVideo":"https://www.youtube.com/embed/f43qOr8eTlU","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"708eaf40-ad8a-4b4f-b9f6-8c4276e08d11","name":"Moksh And His Girlfriend","slug":"moksh-and-his-girlfriend","type":1}],"next":{"id":"8df650ba-ffc6-4622-b357-34779040e18e","name":"Square Root Decomposition","type":1,"slug":"square-root-decomposition"},"prev":{"id":"2684424c-b1dd-4289-b0a2-3ade526b3874","name":"Range Addition","type":1,"slug":"range-addition"}}}
plane

Editor

Loading...

Moksh And His Girlfriend

hard

Recently Moksh(HR of Pepcoding) invented a serum which can increase height of plant by 1 unit. Moksh's girlfriend birthday is next month. He is planning something amazing as a gift for her.His girlfriend's favourite Integer is M. Initially Moksh has N (1 to N) no. of beautiful Rose plants, Each plant can have an Integer height,Initially the height of each plant is zero. Subhesh gives Moksh Q number of operations,In each operation Moksh got two integer start and end and he increases the height of all the plants between start and end position (including start and end) by 1. As Moksh wasn't happy with the pattern of height of the plants formed, He went to Rajneesh and asked him to remove any 1 operation from the Q operations such that the count of plants with height M is maximum possible. Output the maximum possible number of plants with height M. Expected Complexity : O(n+q)

Constraints

Constraint : 2<=N<=100000. 2<=Q<=100000. 1<=M<Q. 1<=L<=R<=N.

Format

Input

First line contains three space separated integer N(no. of Rose plants), Q(number of operations), M. Each of the next Q lines contains two space-separated integers L and R describing one operation.

Output

print a single line containing one integer - the maximum possible number of Trees with height M.

Example

Sample Input

10 3 2 2 6 4 9 1 4

Sample Output

3

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode