5
Your rating: None Average: 5 (1 vote)

CodeChef submission 70955 (C++ 4.0.0-8)

CodeChef submission 70955 (C++ 4.0.0-8) plaintext list. Status: AC, problem INSOMA3, contest . By triplem (Stephen Merriman), 2009-08-16 05:04:49.
  1. #include <iostream>
  2. using namespace std;
  3. int nums[100000];
  4. int ans = 0;
  5. int tmp[100000];
  6. void solve(int low, int high) {
  7.     if (low==high) return;
  8.     int mid = (low+high)/2;
  9.     solve(low,mid);
  10.     solve(mid+1,high);
  11.     // assume [low,mid] is sorted and [mid+1,high] is sorted
  12.     int lowpos = low, highpos = mid+1;
  13.     int tmppos = 0;
  14.     while (lowpos<=mid || highpos<=high) {
  15.         if (lowpos>mid || highpos<=high && nums[highpos]<nums[lowpos]) {
  16.             // take it from the high end
  17.             tmp[tmppos++]=nums[highpos++];
  18.             ans += (mid-lowpos+1);
  19.         } else {
  20.             tmp[tmppos++]=nums[lowpos++];
  21.         }
  22.     }
  23.     tmppos = 0;
  24.     for (int i=low; i<=high; i++) nums[i] = tmp[tmppos++];
  25. }
  26. int main() {
  27.     int N; scanf("%d",&N);
  28.     for (int i=0; i<N; i++) scanf("%d",&nums[i]);
  29.     solve(0,N-1);
  30.     printf("%d\n",ans);
  31.     system("PAUSE");
  32. }
  33.  
  34.

Comments