fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #pragma comment(linker, "/stack:200000000")
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC optimize ("unroll-loops")
  7. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  8.  
  9.  
  10. #define dbg(var) cout<<#var<<"="<<var<<" "
  11. #define ll long long 
  12. #define nl cout<<"\n"
  13. #define fr(i,n) for(int i=0;i<n;i++)
  14. #define rep(i,a,n) for(int i=a;i<n;i++)
  15. #define fast ios::sync_with_stdio(false);cin.tie(0);
  16. #define vi vector<int>
  17. #define vvi vector<vi>
  18. #define pb push_back
  19. #define fa(v) for(auto &i:v)
  20. #define all(v) v.begin(),v.end()
  21. #define sz(x)   (x.size())
  22. #define LSOne(S) (S & (-S))
  23. //////////////   debugger class  starts from here///// 
  24. void __print(int x) {cout << x;}
  25. void __print(long x) {cout << x;}
  26. void __print(long long x) {cout << x;}
  27. void __print(unsigned x) {cout << x;}
  28. void __print(unsigned long x) {cout << x;}
  29. void __print(unsigned long long x) {cout << x;}
  30. void __print(float x) {cout << x;}
  31. void __print(double x) {cout << x;}
  32. void __print(long double x) {cout << x;}
  33. void __print(char x) {cout << '\'' << x << '\'';}
  34. void __print(const char *x) {cout << '\"' << x << '\"';}
  35. void __print(const string &x) {cout << '\"' << x << '\"';}
  36. void __print(bool x) {cout << (x ? "true" : "false");}
  37.  
  38. template<typename T, typename V>
  39. void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
  40. template<typename T>
  41. void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
  42. void _print() {cout << "]\n";}
  43. template <typename T, typename... V>
  44. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
  45. #ifndef ONLINE_JUDGE
  46. #define debug(x...) cout << "[" << #x << "] = ["; _print(x)
  47. #else
  48. #define debug(x...)
  49. #endif
  50.  
  51. ///////  debugger class ends here /////////////
  52.  
  53. const int N=1e5+10;
  54. struct FT {
  55.     vector<ll> ft;
  56.     FT(int n) : ft(n) {}
  57.     ll query(int b) {
  58.         ll sum = 0;
  59.         for (; b; b -= LSOne(b)) sum += ft[b];
  60.         return sum;
  61.     }
  62.  
  63.     void update(int k, int v) {
  64.         for (; k <= N; k += LSOne(k)) ft[k] += v;
  65.     }
  66.  
  67.     void range_update(int i, int j, int v)  {
  68.         update(i, v);
  69.         update(j + 1, -v);
  70.     }
  71. };
  72. int main()
  73. {
  74. //     Case #1: 1 1 2
  75. // Case #2: 1 1 2 2 2 3
  76. fast;
  77.   int tst,T;cin>>tst;T=tst;while(tst--){
  78.     int n;cin>>n;
  79.     cout<<"Case #"<<T-tst<<": ";
  80.     FT bit(N);int mx=0; 
  81.     for(int i=0,x;i<n;i++){
  82.         cin>>x;
  83.         bit.range_update(1,x,1);
  84.         if(bit.query(mx+1)>=mx+1)mx++;
  85.         cout<<mx<<" ";
  86.     }
  87.     nl;
  88.   }  
  89. }
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/houCxv
language:
C++14 (gcc 8.3)
created:
4 years 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!