fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define _nhatminh  int main()
  3. #define ll long long
  4. #define str string
  5. #define fir first
  6. #define sec second
  7. #define ld long double
  8. #define pb push_back
  9. #define MOD 100000009
  10. #define freopen(name) if(fopen(name".INP","r")) {freopen (name".INP","r",stdin); freopen (name".OUT","w",stdout);}
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define piint pair < int , int >
  13. #define piL pair < int , ll>
  14. #define pLL pair < ll , ll >
  15. #define TIME (1.0*clock()/CLOCKS_PER_SEC)
  16. using namespace std;
  17. const int Max_n=1e6;
  18. const int Max_m = 4 * Max_n ;
  19. multiset < int > b[Max_m+3] ;
  20. int s[Max_n+3] ;
  21. int s_size ;
  22. void cal_size(int size) {
  23.     s_size = size;
  24.     for (int i = 0 ; i <= s_size * 2 ; i ++ )
  25.     	s[i] = 1e9 ; 
  26.     for (int i = 0; i < s_size ; i++)
  27.         b[i].clear();
  28. }
  29. void update(int id, int val) {
  30.     id += s_size;
  31.     s[id] = val;
  32.     for ( id /= 2; id > 0; id /= 2){
  33.         s[id] = min(s[2 * id], s[2 * id + 1]);
  34.     }
  35. }
  36. void get(int l, int r, int& res) {
  37.     res = 1e9;
  38.     l += s_size; r += s_size;
  39.     while (l <= r) {
  40.         if (l % 2 == 1) res = min(res, s[l++]);
  41.         if (r % 2 == 0) res = min(res, s[r--]);
  42.         l >>= 1; r >>= 1;
  43.     }
  44. }
  45. int n , l , r , k ; 
  46. ll p[Max_n+3] ;
  47. int a[Max_n+3]; 
  48. int rankQ[Max_n + 1];
  49. int dp[Max_n+1] ;
  50. bool check ( int x ){
  51. 	fill ( p , p + n + 1 , 0 )  ;
  52. 	for (int i = 1 ; i <= n ; i ++ ){
  53. 		p[i] = p[i-1] + a[i-1] ;
  54. 	}
  55. 	ll sortedQ[n + 1] , q[n+1];
  56. 	for (int i = 0 ; i <= n ; i ++ ){
  57. 		q[i] = p[i] - 1ll * x * i ; 
  58. 	}
  59. 	memcpy(sortedQ, q, sizeof(q));
  60. 	sort(sortedQ, sortedQ + n + 1);
  61. 	int m = unique(sortedQ, sortedQ + n + 1) - sortedQ;
  62. 	// what should we do now ? 
  63. 	// 
  64.     for (int i = 0; i <= n; i++)
  65.        rankQ[i] = lower_bound(sortedQ, sortedQ + m, q[i]) - sortedQ;
  66.    for (int i = 0 ; i <= n + 1 ; i ++ )
  67.    		dp[i] = 1e9 ; 
  68.    	dp[0] = 0 ;
  69.    	// truong hop co so 
  70.    	cal_size ( m ) ;
  71.    	// add chi so
  72.  	auto add = [&](int j) {
  73.         int r = rankQ[j];
  74.         b[r].insert(dp[j]);
  75.         update(r, *b[r].begin());
  76.     };
  77.     auto del = [&](int j) {
  78.         int r = rankQ[j];
  79.         auto it = b[r].find(dp[j]);
  80.         if (it != b[r].end()) b[r].erase(it);
  81.         update(r, b[r].empty() ? 1e9 : *b[r].begin());
  82.     };
  83.     for (int i = 1; i <= n; i++) {
  84.         if (i - l >= 0) add(i - l);
  85.         if (i - r - 1 >= 0) del(i - r - 1);
  86.  
  87.         if (i - l >= 0) {
  88.             int r = rankQ[i];
  89.             int minn = 1e9, temp = 1e9;
  90.             get(0, r, minn);
  91.             if (minn < 1e9) minn++;
  92.             get (r + 1, m - 1, temp);
  93.             dp[i] = min(minn, temp);
  94.         }
  95.     }
  96.  
  97.     return dp[n] >= k;
  98. }
  99. //int a[Max_n+3] ;
  100. void solve(){
  101. 	cin >> n >> l >> r >> k ;
  102. 	int max_A = 0 ;
  103. 	for (int i = 0 ; i < n ; i ++ ) {
  104.  
  105. 		cin >> a[i] ;
  106. 		max_A = max ( a[i] , max_A );
  107. 	}
  108. 	int res ; 
  109. 	int lo = 0 , hi = max_A + 1 ;
  110. 	while ( lo <= hi ){
  111. 		int m = ( lo + hi ) >> 1 ;
  112. 		if ( check ( m )){
  113. 			res = m ;
  114. 			lo = m +1  ;
  115. 		}
  116. 		else hi = m - 1 ;
  117. 	}
  118. 	cout << res ; 
  119. }
  120. _nhatminh{
  121. freopen("");
  122. ios_base::sync_with_stdio(0);
  123. cin.tie(0); cout.tie(0);
  124. int q=1;
  125. // cin >> q;
  126. while (q--)
  127. 	solve();
  128. cerr << '\n' << "Time elapsed " << TIME << "s.\n";
  129. return (0);
  130. }
Success #stdin #stdout #stderr 0.06s 195724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
Time elapsed 0.040916s.
https://ideone.com/Q9Buo4
language:
C++14 (gcc 8.3)
created:
2 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!