fork download
copy 
  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. const int maxn = 1e5;
  12. const int INF = 1e9;
  13.  
  14. struct Segment_Tree
  15. {
  16.     int n;
  17.     vector<ii> tree;
  18.     vector<int> lazy;
  19.  
  20.     Segment_Tree(int n = 0) : n(n)
  21.     {
  22.         tree.assign(4 * n + 10, ii(0, 0));
  23.         lazy.assign(4 * n + 10, 0);
  24.     }
  25.     void push(int id)
  26.     {
  27.         if (lazy[id] == 0)
  28.             return ;
  29.         for (int nid = id * 2; nid <= id * 2 + 1; nid++)
  30.         {
  31.             tree[nid].fi += lazy[id];
  32.             tree[nid].se += lazy[id];
  33.             lazy[nid] += lazy[id];
  34.         }
  35.         lazy[id] = 0;
  36.     }
  37.     void update(int id, int l, int r, int u, int v, int val)
  38.     {
  39.         if (r < u || l > v)
  40.             return ;
  41.         if (u <= l && r <= v)
  42.         {
  43.             tree[id].fi += val;
  44.             tree[id].se += val;
  45.             lazy[id] += val;
  46.             return ;
  47.         }
  48.         int m = l + r >> 1;
  49.         push(id);
  50.         update(id << 1, l, m, u, v, val);
  51.         update(id << 1 | 1, m + 1, r, u, v, val);
  52.         tree[id].fi = min(tree[id << 1].fi, tree[id << 1 | 1].fi);
  53.         tree[id].se = max(tree[id << 1].se, tree[id << 1 | 1].se);
  54.     }
  55.     ii get(int id, int l, int r, int u, int v)
  56.     {
  57.         if (r < u || l > v)
  58.             return ii(INF, -INF);
  59.         if (u <= l && r <= v)
  60.             return tree[id];
  61.         int m = l + r >> 1;
  62.         push(id);
  63.         ii a = get(id << 1, l, m, u, v);
  64.         ii b = get(id << 1 | 1, m + 1, r, u, v);
  65.         return ii(min(a.fi, b.fi), max(a.se, b.se));
  66.     }
  67.     void update(int l, int r, int v)
  68.     {
  69.         update(1, 0, n, l, r, v);
  70.     }
  71.     ii get(int l, int r)
  72.     {
  73.         return get(1, 0, n, l, r);
  74.     }
  75. };
  76.  
  77. int n, k;
  78. ll a[maxn + 10];
  79. ii a_sorted[maxn + 10], pre[maxn + 10], suf[maxn + 10];
  80. vector<int> ans;
  81. Segment_Tree st;
  82.  
  83. bool is_intersect(ii a, ii b)
  84. {
  85.     if (a.se > b.se)
  86.         swap(a, b);
  87.     return a.se >= b.fi;
  88. }
  89.  
  90. int main()
  91. {
  92.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  93.     if (fopen("M.INP", "r"))
  94.     {
  95.         freopen("M.INP", "r", stdin);
  96.         freopen("M.OUT", "w", stdout);
  97.     }
  98.  
  99.     cin >> n >> k;
  100.     st = Segment_Tree(n);
  101.     for (int i = 1; i <= n; i++)
  102.     {
  103.         cin >> a[i];
  104.         a_sorted[i] = ii(a[i], i);
  105.         st.update(i, n, 1);
  106.     }
  107.     sort(a_sorted + 1, a_sorted + n + 1);
  108.     for (int i = 1; i <= n; )
  109.     {
  110.         bool flag = 0;
  111.         int j = i;
  112.         while (j < n && a_sorted[i] == a_sorted[j + 1])
  113.             j++;
  114.         for (int k = i; k <= j; k++)
  115.             st.update(a_sorted[k].se, n, -1);
  116.         // if (a_sorted[i].fi == 7)
  117.         // {
  118.         //     for (int i = 0; i <= n; i++)
  119.         //         cout << st.get(i, i).fi << ' ';
  120.         //     el;
  121.         // }
  122.         // 0 0 1 2 3 4 5 6 7 8 7
  123.         int st_1 = max(1, a_sorted[i].se - k + 1);
  124.         int sum = st.get(st_1, st_1).fi;
  125.         pre[st_1] = st.get(0, st_1 - 1);
  126.         for (int p = st_1 + 1; p <= a_sorted[i].se; p++)
  127.         {
  128.             pre[p].fi = min(pre[p - 1].fi, sum);
  129.             pre[p].se = max(pre[p - 1].se, sum);
  130.             if (a[p] < a_sorted[i].fi)
  131.                 sum--;
  132.             if (a[p] > a_sorted[i].fi)
  133.                 sum++;
  134.         }
  135.         int st_2 = min(n, a_sorted[i].se + k - 1);
  136.         sum = st.get(st_2 - 1, st_2 - 1).fi;
  137.         suf[st_2] = st.get(st_2, n);
  138.         for (int p = st_2 - 1; p >= a_sorted[i].se; p--)
  139.         {
  140.             suf[p].fi = min(suf[p + 1].fi, sum);
  141.             suf[p].se = max(suf[p + 1].se, sum);
  142.             if (a[p] < a_sorted[i].fi)
  143.                 sum++;
  144.             if (a[p] > a_sorted[i].fi)
  145.                 sum--;
  146.         }
  147.         // if (a_sorted[i].fi == 7)
  148.         // {
  149.         //     for (int P = st_1; P <= a_sorted[i].se; P++)
  150.         //         cout << pre[P].fi << ' ' << pre[P].se, el;
  151.         //     el;
  152.         //     for (int P = a_sorted[i].se; P <= st_2; P++)
  153.         //         cout << suf[P].fi << ' ' << suf[P].se, el;
  154.         //     el;
  155.         // }
  156.         for (int p = st_1; p <= a_sorted[i].se; p++)
  157.         {
  158.             int np = p + k - 1;
  159.             if (np > n)
  160.                 break;
  161.             // ii pre = st.get(0, p - 1);
  162.             // ii suf = st.get(np, n);
  163.             // if (a_sorted[i].fi == 5)
  164.             //     cout << p - 1 << ' ' << np << ' ' << pre.fi << ' ' << pre.se << ' ' << suf.fi << ' ' << suf.se, el;
  165.             if (is_intersect(pre[p], suf[np]))
  166.             {
  167.                 flag = 1;
  168.                 break;
  169.             }
  170.         }
  171.         // el;
  172.         if (flag)
  173.             ans.push_back(a_sorted[i].fi);
  174.         for (int k = i; k <= j; k++)
  175.             st.update(a_sorted[k].se, n, -1);
  176.         i = j + 1;
  177.     }
  178.     cout << ans.size(), el;
  179.     for (int x : ans)
  180.         cout << x << ' ';
  181. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/6ird1f
language:
C++14 (gcc 8.3)
created:
1 day 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!