-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path10810 - Ultra-QuickSort.cpp
122 lines (97 loc) · 2.75 KB
/
10810 - Ultra-QuickSort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
#define si(x) scanf("%d",&x)
#define sii(x,y) scanf("%d %d",&x,&y)
#define siii(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sll(x,y) scanf("%lld %lld",&x,&y)
#define slll(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define ss(ch) scanf("%s",ch)
#define pi(x) printf("%d",x)
#define pii(x,y) printf("%d %d",x,y)
#define pl(x) printf("%lld",x)
#define pll(x,y) printf("%lld %lld",x,y)
#define sf scanf
#define pf printf
#define pcs(x,y) printf("Case %d: %s", x, y)
#define pci(x,y) printf("Case %d: %d", x, y)
#define pcl(x,y) printf("Case %d: %lld", x, y)
#define NL printf("\n")
#define nl '\n'
#define mod 1000000007
#define FI freopen("in.txt","r",stdin)
#define FO freopen("out.txt","w",stdout)
#define FOR(i,j,k) for(int i = j; i < k; i++)
#define rep(l,n) FOR(l,0,n)
#define per(i,j,k) for(int i = j; i > k; i--)
#define PI acos(-1.0)
#define eps 1e-9
#define pb(x) push_back(x)
#define ppb() pop_back()
#define sz(x) x.size()
#define xx first
#define yy second
#define mp(a,b) make_pair(a,b)
#define ssz(a) strlen(a)
#define mem(ara,val) memset(ara,val,sizeof(ara))
#define clr(ara) mem(ara,0)
#define st(ara) mem(ara,-1)
#define all(a) a.begin(),a.end()
//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#define debug(args...) {dbg,args; cerr<<endl;}
struct debugger{
template<typename T> debugger& operator , (const T& v){
cout<<v<<" ";
return *this;
}
}dbg;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> PII;
typedef vector< PII > VII;
int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};
///=>=>=>=>=>=>=>=>=>00100<=<=<=<=<=<=<=<=<=///
int a[500010];
LL ans;
void solve(int s, int m, int e){
int len1 = m - s + 1;
int len2 = e - m;
VI left, right;
rep(l,len1) left.pb(a[s + l]);
rep(l,len2) right.pb(a[m + l + 1]);
left.pb(999999999 + 10);
right.pb(999999999 + 10);
int x = 0, y = 0;
FOR(l, s, e+1){
if(left[x] <= right[y]) a[l] = left[x++];
else{
a[l] = right[y++];
ans += len1 - x;
}
}
}
void merge_sort(int s, int e){
if(s < e){
int m = (s+e) / 2;
merge_sort(s,m);
merge_sort(m+1,e);
solve(s,m,e);
}
}
int main(){
//std::ios_base::sync_with_stdio(0);cin.tie(0);
//FI;FO;
int t = 0, z = 0, len;
int n, k = 0, m = 0; //int ans = 0;
while(si(n) && n){
ans = 0;
rep(l,n) si(a[l]);
merge_sort(0,n-1);
pl(ans);
NL;
}
return 0;
}