fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. struct Segment_Tree
  12. {
  13.     struct Node
  14.     {
  15.         int mx, mn, lazy;
  16.  
  17.         Node(int mx = 0, int mn = 0, int lazy = 0) :
  18.             mx(mx), mn(mn), lazy(lazy) {};
  19.         Node operator + (int val) const
  20.         {
  21.             return Node(mx + val, mn + val, lazy + val);
  22.         }
  23.         Node operator + (const Node &other) const
  24.         {
  25.             return Node(max(mx, other.mx), min(mn, other.mn), 0);
  26.         }
  27.     };
  28.  
  29.     int n;
  30.     vector<Node> tree;
  31.  
  32.     Segment_Tree(int n = 0) : n(n)
  33.     {
  34.         tree.assign(4 * n + 10, Node(0, 0, 0));
  35.     }
  36.     void push(int id)
  37.     {
  38.         if (tree[id].lazy == 0)
  39.             return ;
  40.         for (int nxt_id = 2 * id; nxt_id <= 2 * id + 1; nxt_id++)
  41.             tree[nxt_id] = tree[nxt_id] + tree[id].lazy;
  42.         tree[id].lazy = 0;
  43.     }
  44.     void update(int id, int l, int r, int u, int v, int val)
  45.     {
  46.         if (r < u || l > v)
  47.             return ;
  48.         if (u <= l && r <= v)
  49.             return tree[id] = tree[id] + val, void();
  50.         int m = l + r >> 1;
  51.         push(id);
  52.         update(id << 1, l, m, u, v, val);
  53.         update(id << 1 | 1, m + 1, r, u, v, val);
  54.         tree[id] = tree[id << 1] + tree[id << 1 | 1];
  55.     }
  56.     Node get(int id, int l, int r, int u, int v)
  57.     {
  58.         if (r < u || l > v)
  59.             return Node(-1e9, 1e9, 0);
  60.         if (u <= l && r <= v)
  61.             return tree[id];
  62.         int m = l + r >> 1;
  63.         push(id);
  64.         return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
  65.     }
  66.     void update(int l, int r, int val)
  67.     {
  68.         update(1, 1, n, l, r, val);
  69.     }
  70.     Node get(int l, int r)
  71.     {
  72.         return get(1, 1, n, l, r);
  73.     }
  74.     void print_tree(int id, int l, int r)
  75.     {
  76.         if (l == r)
  77.             return cout << tree[id].mn << ' ', void();
  78.         int m = l + r >> 1;
  79.         push(id);
  80.         print_tree(id << 1, l, m);
  81.         print_tree(id << 1 | 1, m + 1, r);
  82.     }
  83. };
  84. struct Event
  85. {
  86.     bool is_add;
  87.     int x;
  88.  
  89.     Event(bool is_add = 0, int x = 0) :
  90.         is_add(is_add), x(x) {};
  91. };
  92.  
  93. const int maxn = 3e5;
  94.  
  95. int n, l, q, b[maxn + 10], ans[maxn + 10];
  96. ii a[maxn + 10];
  97. Segment_Tree st;
  98. vector<Event> ev[maxn + 10];
  99. set<int> s;
  100.  
  101. int main()
  102. {
  103.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  104.     if (fopen("STATIS.INP", "r"))
  105.     {
  106.         freopen("STATIS.INP", "r", stdin);
  107.         freopen("STATIS.OUT", "w", stdout);
  108.     }
  109.  
  110.     cin >> n >> l >> q;
  111.     for (int i = 1; i <= n; i++)
  112.     {
  113.         cin >> a[i].fi;
  114.         a[i].se = i;
  115.     }
  116.     sort(a + 1, a + n + 1);
  117.     st = Segment_Tree(n);
  118.     for (int i = 1; i <= n; i++)
  119.     {
  120.         int x = a[i].se;
  121.         st.update(max(l, x), min(n, x + l - 1), 1);
  122.         Segment_Tree::Node res = st.get(max(l, x), min(n, x + l - 1));
  123. //        b[x] = 1;
  124. //        for (int j = 1; j <= n; j++)
  125. //            cout << b[j] << ' ';
  126. //        el;
  127. //        st.print_tree(1, 1, n), el;
  128.         ev[res.mn].push_back(Event(1, a[i].fi));
  129.         ev[res.mx + 1].push_back(Event(0, a[i].fi));
  130.     }
  131.     for (int i = 1; i <= l; i++)
  132.     {
  133.         for (Event e : ev[i])
  134.             if (e.is_add)
  135.                 s.insert(e.x);
  136.             else
  137.                 s.erase(e.x);
  138.         ans[i] = *s.rbegin();
  139.     }
  140.     for (int i = 1; i <= q; i++)
  141.     {
  142.         int x;
  143.         cin >> x;
  144.         cout << ans[x] << ' ';
  145.     }
  146. }
  147.  
Success #stdin #stdout 0.01s 10724KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SHFx7C
language:
C++14 (gcc 8.3)
created:
13 days 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!