Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. #include <fstream>
  2. #include <iostream>
  3. #include <iterator>
  4. #include <math.h>
  5. #include <string.h>
  6. #include <map>
  7. #include <algorithm>
  8. using namespace std;
  9.  
  10. ifstream in("summit.in");
  11. ofstream out("summit.out");
  12.  
  13.  
  14. int n,m;
  15. int v[1000001],aib[1000001];
  16.  
  17. void BUILD(int poz, int val)
  18. {
  19.     for(;poz<=n;poz+=poz&-poz)
  20.         aib[poz]+=val;
  21. }
  22. int SUM(int poz)
  23. {
  24.     int s=0;
  25.     for(;poz;poz-=poz&-poz)
  26.         s+=aib[poz];
  27.     return s;
  28. }
  29.  
  30.  
  31. int BIN(int st, int dr, int val)
  32. {
  33.     while(st<=dr)
  34.     {
  35.         int mij=(st+dr)/2;
  36.         if(aib[mij]==val)
  37.             return mij;
  38.         if(aib[mij]>val)
  39.             dr=mij-1;
  40.         else
  41.             st=mij+1;
  42.     }
  43.     return 0;
  44. }
  45.  
  46. int main()
  47. {
  48.     in>>n;
  49.     for(int i=1; i<=n; i++)
  50.     {
  51.         in>>v[i];
  52.         aib[i]=aib[i-1]+v[i];
  53.     }
  54.     for(int i=1; i<=n; i++)
  55.     {
  56.         out<<BIN(1,n,v[i])<<"\n";
  57.     }
  58.  
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement