fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 1e6 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int n, a[N], k;
  39.  
  40. inline void Read_Input() {
  41.     cin >> n >> k;
  42.     FOR(i, 1, n)
  43.         cin >> a[i];
  44. }
  45.  
  46. struct Segment_Tree {
  47.     int st[4 * N + 5];
  48.  
  49.     void build(int id, int l, int r) {
  50.         memset(st, 0x3f, sizeof(st));
  51.     }
  52.  
  53.     void update(int id, int l, int r, int u, int v, int val) {
  54.         if (l > v || r < u)
  55.             return;
  56.         if (l >= u && r <= v) {
  57.             st[id] = min(st[id], val);
  58.             return;
  59.         }
  60.         int mid = (l + r) >> 1;
  61.         update(id * 2, l, mid, u, v, val);
  62.         update(id * 2 + 1, mid + 1, r, u, v, val);
  63.         st[id] = min(st[id * 2], st[id * 2 + 1]);
  64.     }
  65.  
  66.  
  67.     int Get(int id, int l, int r, int u, int v) {
  68.         if (l > v || r < u)
  69.             return mod;
  70.         if (l >= u && r <= v)
  71.             return st[id];
  72.         int mid = (l + r) >> 1;
  73.         return min(Get(id * 2, l, mid, u, v), Get(id * 2 + 1, mid + 1, r, u, v));
  74.     }
  75.  
  76. }it;
  77.  
  78. inline void Solve() {
  79.     int Ans = INT_MAX;
  80.     vector<int> b(n + 5, 0), pre(n + 5, 0);
  81. //    FOR(i, 1, n) {
  82.     int l = 1, r = 100000;
  83.     while (l <= r) {
  84.         int T = (l + r) >> 1;
  85. //        T = 1;
  86.         FOR(j, 1, n)
  87.             if (a[j] <= T)
  88.                 b[j] = 1;
  89.             else b[j] = -1;
  90.         FOR(j, 1, n)
  91.             pre[j] = pre[j - 1] + b[j];
  92.         /// cay IT ko xu li cho so am .
  93.         /// [-n, n]  => Cong n len de thanh so duong [0, 2 * n]
  94.         it.build(1, 0, 2 * n);
  95.         /// pre[0]
  96.         /// chat nhi phan dap an vi no cang nho cang tot
  97.         bool oke = false;
  98.         FOR(R, 1, n) {
  99.             /// hien tai anh vi tri R va so huu pre[R]
  100.             it.update(1, 0, 2 * n, pre[R - 1] + n, pre[R - 1] + n, R);
  101.             /// pre[L - 1] <= pre[R]
  102.             /// pre[L - 1] = (-n, pre[R]);
  103.             /// get min vi tri cua khoang nay
  104.             /// Don gian bang cay IT;
  105.             /// pre[R] - pre[L - 1] >= 0
  106.  
  107.             int L = it.Get(1, 0, 2 * n, 0, pre[R] + n);
  108.             if (R - L + 1 >= k) {
  109.                 /// suy ra a[i] la 1 dap an co the co
  110.                 oke = true;
  111.                 break;
  112.             }
  113.  
  114.             /// trong tuong lai R1 co the so huu pre[R1] - pre[R - 1] >= 0
  115.             /// R1 - R + 1 >= k
  116.             /// Do do ta can update vi tri cua pre[R - 1] lai
  117.  
  118.         }
  119.  
  120.         if (oke == true) {
  121.             /// T da duoc cong nhan
  122.             Ans = T;
  123.             r = T - 1;
  124.         }
  125.         else l = T + 1;
  126. //        return;
  127.  
  128.     }
  129.     cout << Ans;
  130. }
  131.  
  132. Ti20_ntson {
  133. //    freopen(TASK".INP","r",stdin);
  134. //    freopen(TASK".OUT","w",stdout);
  135.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  136.     int T = 1;
  137. //    cin >> T;
  138.     while (T -- ) {
  139.         Read_Input();
  140.         Solve();
  141.     }
  142. }
  143.  
  144.  
  145. #include <iostream>
  146. using namespace std;
  147.  
  148. int main() {
  149. 	// your code goes here
  150. 	return 0;
  151. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IZMAXT
language:
C++14 (gcc 8.3)
created:
46 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!