Advertisement
SuitNdtie

Plagiarist C00183

Oct 7th, 2019
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. int const N = 200010;
  6. ll fenwick[N];
  7.  
  8. ll query(ll x){
  9. ll sum = 0;
  10. for(int i = x ; i >= 1 ; i -= (i&-i)){
  11. sum += fenwick[i];
  12. }
  13. return sum;
  14. }
  15.  
  16. void update(ll x){
  17. for(int i = x ; i <= N ; i += (i&-i)){
  18. fenwick[i]++;
  19. }
  20. }
  21.  
  22. int main()
  23. {
  24. //freopen("input.txt","r",stdin);
  25. int n;
  26. scanf("%d",&n);
  27. ll arr[n+1];
  28. bool check[n+1];
  29. for(int i = 1 ; i <= n ; i ++){
  30. scanf("%lld",&arr[i]);
  31. check[i] = false;
  32. }
  33. for(int t = 0 ; t < n ; t ++){
  34. ll x;
  35. scanf("%lld",&x);
  36. //// printf("Test : ");for(int i = 1 ; i <= n ; i ++)printf("%d ",i);printf("\n");
  37. // printf("Index : ");
  38. ll l = 1 , r = n;
  39. while(l<=r){
  40. ll m = (l+r)/2;
  41. ll xi = m - query(m);
  42. if(xi == x){
  43. if(check[m]){
  44. r = m - 1;
  45. }
  46. else{
  47. printf("%lld\n",arr[m]);
  48. update(m);
  49. check[m] = true;
  50. break;
  51. }
  52. }
  53. else if(xi > x){
  54. r = m - 1;
  55. }
  56. else{
  57. l = m + 1;
  58. }
  59. }
  60. /* for(int i = 1 ; i <= n ; i ++){
  61. ll xi = i - query(i);
  62. // printf("%lld ",xi);
  63. if(xi == x){
  64. // printf("Test found");
  65. printf("%lld\n",arr[i]);
  66. update(i);
  67. break;
  68. }
  69. }
  70. // printf("\n");*/
  71. }
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement