fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     int maxLen, pre, suf, sz;
  6.     bool active;
  7. };
  8.  
  9. int n, q;
  10. pair<int, int> a[100005]; // Lưu {giá trị, vị trí}
  11. struct Query {
  12.     int k, id;
  13. };
  14. Query queries[100005];
  15. int ans[100005];
  16. Node tree[400005];
  17.  
  18. // Hàm trộn 2 node
  19. Node merge(Node left, Node right) {
  20.     Node res;
  21.     res.sz = left.sz + right.sz;
  22.     res.active = false; // Node cha chỉ active nếu cả 2 con đều active (không cần thiết lắm ở đây)
  23.  
  24.     res.pre = left.pre;
  25.     if (left.pre == left.sz) res.pre += right.pre;
  26.  
  27.     res.suf = right.suf;
  28.     if (right.suf == right.sz) res.suf += left.suf;
  29.  
  30.     res.maxLen = max({left.maxLen, right.maxLen, left.suf + right.pre});
  31.     return res;
  32. }
  33.  
  34. void build(int id, int l, int r) {
  35.     tree[id] = {0, 0, 0, r - l + 1, false};
  36.     if (l == r) return;
  37.     int mid = (l + r) / 2;
  38.     build(2 * id, l, mid);
  39.     build(2 * id + 1, mid + 1, r);
  40. }
  41.  
  42. void update(int id, int l, int r, int pos) {
  43.     if (l == r) {
  44.         tree[id] = {1, 1, 1, 1, true};
  45.         return;
  46.     }
  47.     int mid = (l + r) / 2;
  48.     if (pos <= mid) update(2 * id, l, mid, pos);
  49.     else update(2 * id + 1, mid + 1, r, pos);
  50.     tree[id] = merge(tree[2 * id], tree[2 * id + 1]);
  51. }
  52.  
  53. int main() {
  54.     ios::sync_with_stdio(0); cin.tie(0);
  55.     cin >> n >> q;
  56.     for (int i = 1; i <= n; i++) {
  57.         cin >> a[i].first;
  58.         a[i].second = i;
  59.     }
  60.     sort(a + 1, a + n + 1); // Sắp xếp giá trị mảng để kích hoạt dần dần
  61.  
  62.     for (int i = 0; i < q; i++) {
  63.         cin >> queries[i].k;
  64.         queries[i].id = i;
  65.     }
  66.     sort(queries, queries + q, [](Query x, Query y) {
  67.         return x.k < y.k;
  68.     }); // Sắp xếp truy vấn để xử lý offline
  69.  
  70.     build(1, 1, n);
  71.  
  72.     int idx = 1;
  73.     for (int i = 0; i < q; i++) {
  74.         // "Bật đèn" các phần tử thỏa mãn a[idx].val <= queries[i].k
  75.         while (idx <= n && a[idx].first <= queries[i].k) {
  76.             update(1, 1, n, a[idx].second);
  77.             idx++;
  78.         }
  79.         ans[queries[i].id] = tree[1].maxLen;
  80.     }
  81.  
  82.     for (int i = 0; i < q; i++) cout << ans[i] << "\n";
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5560KB
comments (?)
stdin
copy 
6 4
-2 5 6 10 -5 1
-10
5
-4
11
stdout
copy 
0
2
1
6
https://ideone.com/M1D1mS
language:
C++14 (gcc 8.3)
created:
4 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!