DSA_and_Cpp_Program/sorted_subsegments.cpp at master · Pankaj29Shah/DSA_and_Cpp_Program · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
using namespace std;
void merge(vector<long> *ar,long m,long mid,long n)
{
    //cout<<m<<" "<<n<<endl;
    //cout<<mid<<endl;
    int i=m;
    int j=mid+1;
    int k=m;
    vector<long> sa;
    while(i<=mid && j<=n)
    {
        if((*ar)[i]<=(*ar)[j])
        {
            sa.push_back((*ar)[i]);
            i++;
        }
        else {
            sa.push_back((*ar)[j]);
            j++;
        }
    }
    if(i>mid)
    {
        while(j<=n)
        {
            sa.push_back((*ar)[j]);
            j++;
        }
    }
    else {
        while(i<=mid)
        {
            sa.push_back((*ar)[i]);
            i++;
        }
    }
    int p=0;
    //cout<<sa.size()<<" ";
    for(k=m;k<=n;k++)
    {
        (*ar)[k]=sa.at(p);
        p++;
    }
}
void merge_sort(long m,long n,vector<long>*ar)
{
    //cout<<m<<" "<<n<<endl;
    //cout<<ar<<endl;
    if(m>=n)
    {
        return;
    }
    long mid = (m+n)/2;
    //cout<<mid<<endl;
    merge_sort(m, mid,ar);
    merge_sort(mid + 1,n,ar);
    merge(ar, m, mid, n);
    //for(int i=0;i<n;i++)
    //{
    //    cout<<(*ar)[i]<<" ";
    //}
}
int sortedSubsegments(long k, vector<long> a, vector<long> queries) {
    for(int i=0;i<(queries.size());i++)
    {
        //cout<<queries.at(i)<<" "<<queries.at(i+1)<<endl;
        merge_sort(queries.at(i), (queries.at(i+1)),&a);
         i+=1;
    }
    return a[k];
    //cout<<&a<<endl;
    //for(int i=0;i<a.size();i++)
    //{
    //    cout<<a[i]<<" ";
    //}
}
int main()
{
    long dat;
    vector<long> mn;
    for(int i=0;i<3;i++)
    {
        cin>>dat;
        mn.push_back(dat);
    }
    vector<long> arr;
    for(int i=0;i<mn.at(0);i++)
    {
        cin>>dat;
        arr.push_back(dat);
    }
    vector<long> q;
    for(int i=0;i<(mn.at(1)*2);i++)
    {
        cin>>dat;
        q.push_back(dat);
    }
    //sortedSubsegments(mn[2],arr,q);
    //cout<<&arr<<endl;
    cout<<"\n"<<sortedSubsegments(mn[2],arr,q);
    return 0;
}