fork(1) download 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <iostream>
  4. #include <cassert>
  5.  
  6. struct Node {
  7.     int sum, leftId, rightId;
  8.  
  9.     Node(int low, int high, int idl = -1, int idr = -1)
  10.         : sum(high-low+1), leftId(idl), rightId(idr)
  11.     { }
  12. };
  13.  
  14. struct SegmentTree {
  15.  
  16.     const int left, right;
  17.  
  18.     std::vector<Node> tree;
  19.  
  20.     void extend(int id, int l, int r)
  21.     {
  22.         // Check on estimated max size
  23.         assert(tree.size() <= (1u << 21) + (1u << 20));
  24.  
  25.         if (tree[id].leftId == -1) {
  26.             int mid = (l + r) >> 1;
  27.  
  28.             tree.push_back(Node(l, mid));
  29.             tree[id].leftId = (int)tree.size()-1;
  30.  
  31.             tree.push_back(Node(mid+1, r));
  32.             tree[id].rightId = (int)tree.size()-1;
  33.         }
  34.     }
  35.  
  36.     void update(int index, int delta, int id, int l, int r) {
  37.         if (index < l || index > r) {
  38.             return;
  39.         }
  40.  
  41.         if (l == r) {
  42.             tree[id].sum += delta;
  43.             return;
  44.         }
  45.  
  46.         extend(id, l, r);
  47.  
  48.         const int idl = tree[id].leftId;  assert(idl != -1);
  49.         const int idr = tree[id].rightId; assert(idr != -1);        
  50.         const int m = (l+r)/2;
  51.  
  52.         update(index, delta, idl,   l, m);
  53.         update(index, delta, idr, m+1, r);
  54.  
  55.         tree[id].sum = tree[idl].sum + tree[idr].sum;
  56.     }
  57.  
  58.     void update(int index, int delta) {
  59.         return update(index, delta, 0, left, right);
  60.     }
  61.  
  62.     int query(int k, int id, int l, int r) {
  63.         if (l == r) {
  64.             return l;
  65.         }
  66.  
  67.         extend(id, l, r);
  68.  
  69.         const int idl = tree[id].leftId;  assert(idl != -1);
  70.         const int idr = tree[id].rightId; assert(idr != -1);        
  71.         const int m = (l+r)/2;
  72.  
  73.         if (tree[idl].sum >= k) {
  74.             return query(k, idl, l, m);
  75.         } else {
  76.             return query(k - tree[idl].sum, idr, m+1, r);
  77.         }
  78.     }
  79.  
  80.     int query(int k) {
  81.         return query(k, 0, left, right);
  82.     }
  83.  
  84.     SegmentTree(int l, int r) : left(l), right(r) {
  85.         tree.reserve((1u << 21) + (1u << 20)); // Reserve estimated max size Nodes
  86.         tree.push_back(Node(l, r));
  87.     }
  88. };
  89.  
  90. int main() {
  91.     int n, m, num;
  92.     char op;
  93.  
  94.     scanf("%d%d", &n, &m);
  95.  
  96.     SegmentTree st(1, n);
  97.  
  98.     for (int i = 1; i <= m; i++) {
  99.         scanf(" %c %d", &op, &num);
  100.         int q = st.query(num);
  101.         if (op == 'L') {
  102.             printf("%d\n", q);
  103.         } else {
  104.             st.update(q, -1);
  105.         }
  106.     }
  107.     return 0;
  108. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin 
20 7
L 5
D 5
L 4
L 5
D 5
L 4
L 5
stdout 
5
4
6
4
7
https://ideone.com/O101LR
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!