Question Name:Sonam Bewafa asks questions

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <climits>
#include <stdlib.h>
#include <time.h>
#include <cassert>
#include <map>
#include <unordered_set>
#include <bitset>
#include <list>
#include <climits>
#include <unordered_map>

using namespace std;


int main(){
    
    int t;
    
    cin >> t;
    
    while(t--){
      
        int n,q;
        cin >> n >> q;
        vector<pair <long long,long long>> arr(n);
        int i;
        for(i=0;i<n;i++){
            long long a,b;
            cin >> a >> b;
            arr[i]={a,b};
        }
        vector <long long> brr(n);
        for(i=0;i<n;i++){
            if(i==0){
                brr[i]=arr[i].first-1;
            }
            else{
                brr[i]=arr[i].first-arr[i-1].second-1+brr[i-1];
            }
        }
        for(i=0;i<n;i++){
            arr[i].first=arr[i].first-brr[i];
            arr[i].second=arr[i].second-brr[i];
        }
        arr[n-1].second=pow(10, 18);
        while (q--) {
            long long x;
            cin >> x;
            int l=0;
            int h=n-1;
            int ans=0;
            while (l<=h) {
                int mid=(l+h)/2;
                if(x>=arr[mid].first && x<=arr[mid].second){
                    ans=mid;
                    break;
                }
                else if(x<arr[mid].first){
                    h=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
           
            cout << x+brr[ans] << " " ;
            
            
        }
        cout << endl;
        
        
    }
    return 0;
    //sujan
}


Problem Description

They declared Sonam as bewafa . Although she is not, believe me! She asked a number of queries to people regrading their position in a test. Now its your duty to remove her bewafa tag by answering simple queries.

All the students who give test can score from 1 to 10^18. Lower the marks , better the Rank. Now instead of directly telling the marks of student they have been assigned groups where marks are distributed in continuous intervals, you have been given l(i) lowest mark of interval i and r(i) highest marks in interval i. So marks distribution in that interval is given as l(i), l(i)+1, l(i)+2 . . . r(i).

Now Sonam ask queries in which she gives rank of the student (x) and you have to tell marks obtained by that student.

Note: rank1 is better than rank2 and rank2 is better than rank3 and so on and the first interval starts from 1.

Input:
The first line of input contains an integer T, denoting the no of test cases. Then T test cases follow. Each test case contains two space separated values N and Q denoting the no of groups and no of queries asked respectively.

The next line contains N group of two integers separated by space which shows lowest marks in group i ie l(i) and highest marks in group i ie r(i) such that if i < j then r(i) < l(j). The next lines contain Q space separated integers x, denoting rank of student.

Output:
For each query output marks obtain by student whose rank is x(1<=x<=10^18).

Constraints:
1<=T<=50
1<=N<=10^5
1<=Q<=10^5
1<= l(i) < r(i) <=10^18
1<=x<=10^18

  • Test Case 1

    Input (stdin)

    1
    3 3
    1 10 12 20 22 30
    5 15 25
    

    Expected Output

    5 16 27
  • Test Case 2

    Input (stdin)

    1
    3 3
    1 10 15 20 21 30
    5 11 23
    
    

    Expected Output

    5 15 27 

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.