fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<algorithm>
  5. #include<cstdio>
  6. #include<cmath>
  7. #include<cstdlib>
  8. #include<cstring>
  9. #include<queue>
  10. #include<fstream>
  11. #include<sstream>
  12. #include<stack>
  13. #include<list>
  14. #include<deque>
  15. #include<bitset>
  16. #include<utility>
  17. #include<climits>
  18. #include<iomanip>
  19. #include<ctime>
  20. #include<complex>
  21. using namespace std;
  22.  
  23.  
  24. #define FOR(i,a,b) for (int i=(a);i<(b);i++)
  25. #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
  26. #define REP(i,n) for (int i=0;i<(n);i++)
  27. #define RREP(i,n) for (int i=(n)-1;i>=0;i--)
  28.  
  29. #define inf INT_MAX/3
  30. #define pb push_back
  31. #define mp make_pair
  32. #define all(a) (a).begin(),(a).end()
  33. #define SET(a,c) memset(a,c,sizeof a)
  34. #define CLR(a) memset(a,0,sizeof a)
  35. #define pii pair<int,int>
  36. #define pcc pair<char,char>
  37. #define pic pair<int,char>
  38. #define pci pair<char,int>
  39. #define VS vector<string>
  40. #define VI vector<int>
  41. #define debug(x) cout<<#x<<": "<<x<<endl
  42. #define MIN(a,b) (a>b?b:a)
  43. #define MAX(a,b) (a>b?a:b)
  44. #define pi 2*acos(0.0)
  45. #define INFILE() freopen("in0.txt","r",stdin)
  46. #define OUTFILE()freopen("out0.txt","w",stdout)
  47. #define in scanf
  48. #define out printf
  49. #define ll unsigned long long
  50.  
  51.  
  52.  
  53. #define Mx 100015
  54. string str;
  55.  
  56. ll len;
  57. ll tree[4*Mx];
  58.  
  59. void insert(int cur , int st , int ed , int pos)
  60. {
  61.     if(st==ed && st==pos)
  62.     {
  63.         tree[cur]++;
  64.         return ;
  65.     }
  66.  
  67.     int mid,lft,rgt;
  68.     mid=(st+ed)/2;
  69.     lft=2*cur;
  70.     rgt=lft+1;
  71.  
  72.     if(pos<=mid)
  73.     {
  74.         insert(lft,st,mid,pos);
  75.     }
  76.     else insert(rgt,mid+1,ed,pos);
  77.  
  78.     tree[cur]=tree[lft]+tree[rgt];
  79. }
  80.  
  81. int query(int cur , int st , int ed , int x , int y)
  82. {
  83.     if(x>y)return 0;
  84.  
  85.     if(st==x && ed==y)
  86.     {
  87.         return tree[cur];
  88.     }
  89.     int mid,lft,rgt;
  90.     mid=(st+ed)/2;
  91.     lft=2*cur;
  92.     rgt=lft+1;
  93.  
  94.     if(y<=mid)return query(lft,st,mid,x,y);
  95.     else if(x>mid)return query(rgt,mid+1,ed,x,y);
  96.     else
  97.     {
  98.         int a=query(lft,st,mid,x,mid);
  99.         int b=query(rgt,mid+1,ed,mid+1,y);
  100.         return a+b;
  101.     }
  102.  
  103. }
  104.  
  105.  
  106. int main()
  107. {
  108.  
  109.     int i,j,k;
  110.     int cas,ks;
  111.     cin>>ks;
  112.     FOR(cas,1,ks+1)
  113.     {
  114.         cin>>len;
  115.         int nn=(4*len)+5;
  116.         //SET(tree,0);
  117.         FOR(i,0,nn)tree[i]=0;
  118.         cin>>str;
  119.  
  120. //        scanf("%s",str);
  121.         int high=0;
  122.  
  123.  
  124.         ll sz=0;
  125.         ll con=0;
  126.         ll res=0;
  127.  
  128.         for(i=0; i<len; i++)
  129.         {
  130.             if(str[i]=='4')
  131.             {
  132.                 con=1;
  133.                 sz=sz+1;
  134.  
  135.             }
  136.             else if(str[i]=='7')
  137.             {
  138.  
  139.                 if(sz==0)
  140.                 {
  141.                     con=1;
  142.                 }
  143.                 else
  144.                 {
  145.                     ll bad=0;
  146.                     bad=query(1,1,len,1,con-1 );
  147.  
  148.  
  149.                     res=res+( i - (2*bad) );
  150.  
  151.  
  152.                     insert(1,1,len,con);
  153.                     con++;
  154.                     sz=sz-1;
  155.                 }
  156.             }
  157.         }
  158.         cout<<res<<endl;
  159.  
  160.     }
  161.  
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0s 6560KB
comments (?)
stdin
copy 
1
183
474777474747474444474477777474744474747477774744444474474747447474747474747474747774774744747474747474747474747474747474747474747474747444447777747474747474744747474747474444474774777
stdout
copy 
6883
https://ideone.com/XyIoYh
language:
C++ (gcc 8.3)
created:
10 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!