| Home | Contests | Problems | Status | Standing | Register | Login |
Problem F
Description 
Problem B: Ultra-QuickSortIn this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of ndistinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence9 1 0 5 4 ,Ultra-QuickSort produces the output 0 1 4 5 9 .Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence. The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed. For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence. Sample Input5 9 1 0 5 4 3 1 2 3 0 Output for Sample Input6 0 Stefan B�ttcher |
 |
0
Initialization.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define LOW(x) ((x)&(-x))
int n;
int c[500010];
void mod ( int x, int v ) {
while ( x <= n ) {
c[x] += v;
x += LOW ( x );
}
}
long long sum ( int x ) {
long long s = 0;
while ( x > 0 ) {
s += c[x];
x -= LOW ( x );
}
return s;
}
int main()
{
while(~scanf("%d",&n), n)
{
int i ;
memset ( c, 0, sizeof (c) );
vector<int> v ;
for(i = 0 ; i < n ; i++)
{
int t ;
scanf("%d",&t);
v.push_back(t);
}
vector <int> p(v);
sort ( p.begin (), p.end () );
vector <int>::iterator end = unique ( p.begin(), p.end () );
for ( i = 0; i < n; ++ i ) {
v[i] = lower_bound ( p.begin(), end, v[i] ) - p.begin() + 1;
}
long long res = 0;
for ( i = n-1; i >= 0; -- i ) {
res += sum ( v[i]-1 );
mod ( v[i], 1 ) ;
}
printf ( "%lld\n", res );
}
return 0;
}
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define LOW(x) ((x)&(-x))
int n;
int c[500010];
void mod ( int x, int v ) {
while ( x <= n ) {
c[x] += v;
x += LOW ( x );
}
}
long long sum ( int x ) {
long long s = 0;
while ( x > 0 ) {
s += c[x];
x -= LOW ( x );
}
return s;
}
int main()
{
while(~scanf("%d",&n), n)
{
int i ;
memset ( c, 0, sizeof (c) );
vector<int> v ;
for(i = 0 ; i < n ; i++)
{
int t ;
scanf("%d",&t);
v.push_back(t);
}
vector <int> p(v);
sort ( p.begin (), p.end () );
vector <int>::iterator end = unique ( p.begin(), p.end () );
for ( i = 0; i < n; ++ i ) {
v[i] = lower_bound ( p.begin(), end, v[i] ) - p.begin() + 1;
}
long long res = 0;
for ( i = n-1; i >= 0; -- i ) {
res += sum ( v[i]-1 );
mod ( v[i], 1 ) ;
}
printf ( "%lld\n", res );
}
return 0;
}