Sgu 180
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" vector<long long> m; vector<long long> m1; vector<long long> m2; long long Merge(int l, int mm, int r) { int n1,n2,i1,i2; long long c = 0; n1 = n2 = i1 = i2 = 0; for(int i = l; i <= mm; i++) { m1[n1] = m[i]; n1 ++; } m1[n1] = INT_MAX; for(int i = mm + 1; i <= r; i++) { m2[n2] = m[i]; n2 ++; } m2[n2] = INT_MAX; for(int i = l; i <= r; i++) { if(m1[i1] <= m2[i2]) { m[i] = m1[i1]; i1++; } else { m[i] = m2[i2]; i2++; c += (long long)(n1 - i1); } } return c; } long long MergeSort(int l, int r) { if(r > l) { int m = (l+r)/2; long long a = MergeSort(l, m); long long b = MergeSort(m + 1, r); long long c = Merge(l,m,r); return a + b + c; } return 0; } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int n; cin >> n; m.resize(n+10); m1.resize(n+10); m2.resize(n+10); int t; for(int i = 0; i < n; i++) { cin >> t; m[i+1] = t; } cout << MergeSort(1, n) << endl; }
page revision: 0, last edited: 13 Jul 2008 13:51