1 #include<cstdio>

 2 #include<queue>
 3 #include<vector>
 4 using namespace std;
 5 struct cmp
 6 {
 7     bool operator()(int x, int y)
 8     {
 9         return x > y;
10     }
11 };
12 priority_queue<int, vector<int>, cmp>q;
13 int main(int argc, char const *argv[]) 
14 {
15     int n, k, temp;
16     char str[2];
17     //freopen("in.c", "r", stdin);
18     while(~scanf("%d%d", &n, &k))
19     {
20         while(!q.empty())
21             q.pop();
22         for(int i = 0;i < n;i ++)
23         {
24             scanf("%s", str);
25             if(str[0] == ‘I‘)
26             {
27                 scanf("%d", &temp);
28                 q.push(temp);
29                 if(q.size() > k)
30                     q.pop();
31             }
32             else
33                 printf("%d\n", q.top());
34         }
35     }
36     return 0;
37 }

 1 #include<stdio.h>
 2 #define MAX 1000005
 3 typedef struct
 4 {
 5     int left, right, mid, num, l_cnt, r_cnt;
 6 }NodeTree;
 7 NodeTree node[4*MAX];
 8 void BuildTree(int k, int l, int r)
 9 {
10     node[k].left = l;
11     node[k].right = r;
12     node[k].l_cnt = node[k].r_cnt = 0;
13     node[k].mid = (l + r) >> 1;
14     if(l == r)
15         return;
16     int mid = (l + r) >> 1;
17     BuildTree(k << 1, l, mid);
18     BuildTree(k << 1|1, mid+1, r);
19 }
20 
21 void UpdateTree(int k, int num)
22 {
23     if(node[k].left == node[k].right)
24     {
25         node[k].num = num;
26         return ;
27     }
28     if(node[k].mid < num)
29     {
30         node[k].r_cnt ++;
31         UpdateTree(k << 1|1, num);
32     }
33     else
34     {
35         node[k].l_cnt ++;
36         UpdateTree(k << 1, num);
37     }
38 }
39 
40 int GetRusult(int k, int pos)
41 {
42     if(node[k].left == node[k].right)
43         return node[k].num;
44     if(node[k].r_cnt >= pos)
45         GetRusult(k << 1|1, pos);
46     else
47         GetRusult(k << 1, pos - node[k].r_cnt);
48 }
49 
50 int main(int argc, char const *argv[]) 
51 {
52     int n, k, a, i;
53     char str[2];
54     //freopen("in.c", "r", stdin);
55     while(~scanf("%d%d", &n, &k))
56     {
57         BuildTree(1, 1, n);
58         for(i = 0;i < n;i ++)
59         {
60             scanf("%s", str);
61             if(str[0] == ‘I‘)
62             {
63                 scanf("%d%d", &a);
64                 UpdateTree(1, a);
65             }
66             else
67             {
68                 printf("%d\n", GetRusult(1, k));
69             }
70         }
71     }
72     return 0;
73 }