fork(3) download
copy 
  1. #pragma GCC optimize("O3", "unroll-loops")
  2. // God Help me !!
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. // #define watch(x) cout << (#x) << " is " << (x) << endl
  6.  
  7. #define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
  8. #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  9. #define FIXED cout << fixed << setprecision(20)
  10. #define RANDOM srand(time(nullptr))
  11. #define int long long
  12. #define sz(a) (int)a.size()
  13. #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
  14. #define sep(i,a,b) for(int i=(int)a;i>=(int)b;i--)
  15. #define inf 0x3f3f3f3f
  16. #define pb push_back
  17. #define mp make_pair
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define all(a) a.begin(),a.end()
  21. #define x first
  22. #define y second
  23. #define endl "\n"
  24. #define n6 3000005
  25. #define n3 3005
  26. #define n5 300005
  27.  
  28. #define pi pair<int,int>
  29. #define pii pair<int,pi>
  30.  
  31. #define dbg1(x)                cout << #x << ": " << x << endl;
  32. #define dbg2(x, y)             cout << #x << ": " << x << " | " << #y << ": " << y << endl;
  33. #define dbg3(x, y, z)          cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  34. #define dbg4(a, b, c, d)       cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  35. #define dbg5(a, b, c, d, e)    cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  36. #define dbg6(a, b, c, d, e, f) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  37.  
  38. #define dbg(...) fprintf(stderr, __VA_ARGS__)
  39. #define dbgv(x) cout << #x << " = " << x << endl
  40. #define dbga(arr, len) {cout << #arr << " = "; for (int _ = 0; _ < len; _++)\
  41. cout << arr[_] << " "; cout << endl;}
  42. #define dbgi(it) {cout << #it << " = "; for (const auto& _ : it)\
  43. cout << _ << " "; cout << endl;}
  44.  
  45. const int md = (int) 1e9 + 7;
  46.  
  47. inline void add(int &a, int b) {
  48.   a += b;
  49.   if (a >= md) a -= md;
  50. }
  51.  
  52. inline void sub(int &a, int b) {
  53.   a -= b;
  54.   if (a < 0) a += md;
  55. }
  56.  
  57. inline int mul(int a, int b) {
  58.   return (int) ((long long) a * b % md);
  59. }
  60.  
  61. inline int power(int a, long long b) {
  62.   int res = 1;
  63.   while (b > 0) {
  64.     if (b & 1) {
  65.       res = mul(res, a);
  66.     }
  67.     a = mul(a, a);
  68.     b >>= 1;
  69.   }
  70.   return res;
  71. }
  72.  
  73.  
  74. void solve_util(int m, int &cnt, int &sum){
  75.  
  76.  
  77. }
  78.  
  79. const int K = 27;
  80. int st[n5][K];
  81. int arr[n5];
  82. int N;
  83. int h,b,e;
  84.  
  85. int logi[n5];
  86. void precompute_log(){
  87.     logi[1] = 0;
  88.     for (int i = 2; i <= n5; i++)
  89.         logi[i] = logi[i/2] + 1;
  90. }
  91.  
  92.  
  93. int range_sum(int L, int R){
  94.     long long sum = 0;
  95.     for (int j = K; j >= 0; j--) {
  96.         if ((1 << j) <= R - L + 1) {
  97.             sum += st[L][j];
  98.             L += 1 << j;
  99.         }
  100.     }
  101.     return sum;
  102. } 
  103.  
  104.  
  105. void RMQ(){  
  106.  
  107.     for (int i = 0; i < N; i++)
  108.         st[i][0] = arr[i];
  109.  
  110.     for (int j = 1; j <= K; j++)
  111.         for (int i = 0; i + (1 << j) <= N; i++)
  112.             st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
  113.  
  114. }
  115.  
  116. int ans = 0;
  117. int RMQutil(int L, int R){
  118.     int j = logi[R - L + 1];
  119.     int maxi = min(st[L][j], st[R - (1 << j) + 1][j]);
  120.     return maxi;
  121. }
  122.  
  123. void solve(){
  124.     while(cin>>N>>h>>b>>e){
  125.         // cout<<N<<h<<b<<e<<endl;
  126.         int n = N;
  127.         rep(i,0,N-1)cin>>arr[i];
  128.         // dbga(arr, N);
  129.         b--;e--;
  130.         RMQ();
  131.         // dbgv(l);dbgv(r);
  132.         // int brr[n5];
  133.         vector<int> brr(n,0);
  134.         // memset(brr, 1, sizeof(brr));
  135.         for(int i=b;i<=e;){
  136.             for(int j=i+1;j<=e;j++){
  137.                 if(i+1<=e and arr[i]==arr[i+1]){
  138.                     brr[i] = 1;
  139.                     brr[i+1] = 1;
  140.                     i+=2;
  141.                     break;
  142.                 }
  143.                 if(RMQutil(i+1,j)<arr[i]){
  144.                     // cout<<" loop1 ";
  145.                     brr[i] = 1;
  146.                     // dbgv(i);dbgv(j);dbgv(j-i);
  147.                     i+=j-i;
  148.                     // dbgv(i);dbgv(j);dbgv(j-i);
  149.                     break;
  150.                 }
  151.                 else{
  152.                     // cout<<" loop2 ";
  153.                     // dbgv(i);dbgv(j);dbgv(j-i);
  154.                     brr[i] = j-i+1;
  155.                 }
  156.                 if(j==e)i+=j-i+1;
  157.             }
  158.             // dbgi(brr);
  159.         }
  160.         rep(i,b,e){
  161.             cout<<brr[i]<<" ";
  162.         }
  163.         cout<<"\n";
  164.     }
  165. }
  166.  
  167. signed main()
  168. {
  169.     FAST; FIXED; RANDOM;
  170.     int t=1;
  171.     precompute_log();
  172.     // cin>>t;
  173.     // time_t time_t1, time_t2;
  174.     // time_t1 = clock();
  175.     while(t--)
  176.         solve();
  177.  
  178.     // time_t2 = clock();
  179.     // cout << "time taken :" << time_t2 - time_t1 << endl;
  180.     return 0;
  181. }
Success #stdin #stdout 0s 83200KB
comments (?)
stdin
copy 
6 3 1 6
5 4 4 3 5 6
3 3 2 3
9000 9000 9000
stdout
copy 
1 1 1 3 0 0 
1 1
https://ideone.com/h9MnMR
problem TNVFC1M, based on SPOJ submission 22899258 (CPP14), 2018-12-18 08:17:16
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!