fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. struct node {
  8.     int sum;
  9.     node *left, *right;
  10.  
  11.     node(int low, int high)
  12.     {
  13.         sum = (high - low + 1);
  14.         left = NULL;
  15.         right = NULL;
  16.     }
  17.  
  18.     void extend(int l, int r)
  19.     {
  20.         if (left == NULL) {
  21.             int mid = (l + r) >> 1;
  22.             left = new node(l, mid);
  23.             right = new node(mid + 1, r);
  24.         }
  25.     }
  26. };
  27.  
  28. node* Root;
  29.  
  30. void updateSegTree(int index, int delta, node* root, int l, int r)
  31. {
  32.     if (index < l || index > r)
  33.         return;
  34.  
  35.     if (l == r) {
  36.         root->sum += delta;
  37.         return;
  38.     }
  39.  
  40.     root->extend(l, r);
  41.     updateSegTree(index, delta, root->left, l, (l+r) / 2);
  42.     updateSegTree(index, delta, root->right, (l+r) / 2 + 1, r);
  43.     root->sum = (root->left)->sum + (root->right)->sum;
  44. }
  45.  
  46. int query(int k, node* root, int l, int r)
  47. {
  48.     if (l == r)
  49.         return l;
  50.  
  51.     root->extend(l, r);
  52.     if ((root->left)->sum >= k)
  53.         return query(k, root->left, l, (l+r)/2);
  54.     return query(k - ((root->left)->sum), root->right, (l+r)/2+1, r);
  55. }
  56.  
  57. int main()
  58. {
  59.     //std::cerr << sizeof(node) << std::endl;
  60.     int n, m, num;
  61.     char op;
  62.  
  63.     scanf("%d%d", &n, &m);
  64.  
  65.     Root = new node(1, n);
  66.  
  67.     for (int i = 1; i <= m; i++) {
  68.         scanf(" %c %d", &op, &num);
  69.         int q = query(num, Root, 1, n);
  70.         if (op == 'L')
  71.             printf("%d\n", q);
  72.         else
  73.             updateSegTree(q, -1, Root, 1, n);
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0s 4568KB
comments (?)
stdin
copy 
20 7
L 5
D 5
L 4
L 5
D 5
L 4
L 5
stdout
copy 
5
4
6
4
7
https://ideone.com/IUoNeG
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!