fork download
copy 
  1. /* 
  2.  *
  3.  * Author: srkrishnan
  4.  *
  5.  * Created on July 28, 2011, 5:26 PM
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #define MAX 1024
  11.  
  12. void init(int *fw) {
  13.     int i = 0;
  14.     for (i = 0; i < MAX; i++) {
  15.         fw[i] = 0;
  16.     }
  17. }
  18.  
  19. int getCumFrq(int *fw, int i) {
  20.     int cumfrq = 0;
  21.     while (i > 0) {
  22.         cumfrq += fw[i];
  23.         i = i - (i & -i);
  24.     }
  25.     return cumfrq;
  26. }
  27.  
  28. void update(int *fw, int i) {
  29.     while (i < MAX) {
  30.         fw[i]++;
  31.         i = i + (i & -i);
  32.     }
  33. }
  34.  
  35. void solve(int *a, int n, int *ans, int *fw) {
  36.     int i = 0;
  37.     for (i = n - 1; i >= 0; i--) {
  38.         ans[i] = getCumFrq(fw, a[i]);
  39.         update(fw,a[i]);
  40.     }
  41. }
  42.  
  43. int main(int argc, char** argv) {
  44.  
  45.     int a[] = {7, 5, 2, 5, 3, 4, 10, 2, 7, 1, 2, 3, 1, 6, 9};
  46.     int n = sizeof (a) / sizeof (a[0]);
  47.     int ans[n], fw[MAX], i = 0;
  48.  
  49.     init(fw);
  50.     solve(a, n, ans, fw);
  51.  
  52.     for (i = 0; i < n; i++) {
  53.         printf(" %d ", ans[i]);
  54.     }
  55.  
  56.     return (EXIT_SUCCESS);
  57. }
  58.  
Success #stdin #stdout 0s 1720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 12  9  4  7  5  5  8  3  5  1  1  1  0  0  0
https://ideone.com/IaU3F
language:
C (gcc 8.3)
created:
14 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!