fork download
copy 
  1. //#pragma comment(linker, "/STACK:16777216")
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <algorithm>
  6. #include <string>
  7. #include <cstring>
  8. #include <vector>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <map>
  13. #include <set>
  14. #include <limits>
  15. #include <climits>
  16. #include <cmath>
  17. #include <functional>
  18. #include <ctime>
  19. #include <cstdlib>
  20. #include <fstream>
  21. #include <typeinfo>
  22. #include <cassert>
  23.  
  24. #define endl '\n'
  25. #define remainder safdskhaslfa
  26. #define pow aafkhffhlgsdas
  27. #define distance dagkjsdsdsara
  28. #define left askfjasieqwskajdaks
  29. #define right sakjjlkjlkjlashfjas
  30. #define y0 kshjlhlliahjajkdhkasfdg
  31. #define y1 kjlajhjaskhajkhjfkahgjahjkas
  32.  
  33. using namespace std;
  34.  
  35. const int SIZE = 1<<17;
  36.  
  37. int n,tests;
  38. int a[SIZE],x[SIZE];
  39. int best;
  40. long long inv_cnt,max_inv;
  41.  
  42. struct fenwick_tree {
  43. 	int a[SIZE];
  44. 	void Initialize() {
  45. 		memset(a,0,sizeof(a));
  46. 	}
  47. 	void Update(int pos, int val) {
  48. 		for(;pos<SIZE;pos+=pos&(-pos)) a[pos]+=val;
  49. 	}
  50. 	int Query(int pos) {
  51. 		int ans=0;
  52. 		for(;pos>=1;pos-=pos&(-pos)) ans+=a[pos];
  53. 		return ans;
  54. 	}
  55. }it;
  56.  
  57. int next(int p) {
  58. 	p++;
  59. 	if(p>n) p=1;
  60. 	return p;
  61. }
  62.  
  63. bool compare(int idx1, int idx2) {
  64. 	int cnt;
  65. 	for(cnt=1;cnt<=min(n,1000);cnt++,idx1=next(idx1),idx2=next(idx2)) {
  66. 		if(a[idx1]<a[idx2]) return true;
  67. 		if(a[idx1]>a[idx2]) return false;
  68. 	}
  69. 	return false;
  70. }
  71.  
  72. int main() {
  73.   ios_base::sync_with_stdio(false);
  74.   cin.tie(NULL);
  75.   //ifstream cin("test.txt");
  76.   //freopen("test.txt","r",stdin);
  77.   int i,left,right,middle;
  78.  
  79.   cin>>tests;
  80.   while(tests--) {
  81. 		cin>>n;
  82. 		for(i=1;i<=n;i++) cin>>a[i];
  83. 		for(i=1;i<=n;i++) x[i]=a[i];
  84. 		sort(x+1,x+1+n);
  85. 		for(i=1;i<=n;i++) {
  86. 			if(a[i]==x[1]) a[i]=1;
  87. 			else {
  88. 				left=1;
  89. 				right=n;
  90. 				while(right-left>1) {
  91. 					middle=(left+right)>>1;
  92. 					if(x[middle]<a[i]) left=middle;
  93. 					else right=middle;
  94. 				}
  95. 				a[i]=right;
  96. 			}
  97. 		}
  98. 		//for(i=1;i<=n;i++) assert(a[i]>=1 && a[i]<SIZE);
  99.  
  100. 		it.Initialize();
  101. 		inv_cnt=0;
  102. 		for(i=n;i>=1;i--) {
  103. 			inv_cnt+=it.Query(a[i]-1);
  104. 			it.Update(a[i],1);
  105. 		}
  106. 		max_inv=inv_cnt;
  107. 		best=0;
  108. 		for(i=1;i<n;i++) {
  109. 			inv_cnt-=it.Query(a[i]-1);
  110. 			inv_cnt+=it.Query(SIZE-1)-it.Query(a[i]);
  111. 			if(inv_cnt>max_inv) {
  112. 				max_inv=inv_cnt;
  113. 				best=i;
  114. 			}
  115. 			else if(inv_cnt==max_inv) {
  116. 				if(compare(i+1,best+1)) best=i;
  117. 			}
  118. 		}
  119. 		cout<<best<<' '<<max_inv<<endl;
  120.   }
  121.  
  122.   return 0;
  123. }
  124.  
Success #stdin #stdout 0s 4772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mAceb4
language:
C++14 (gcc 8.3)
created:
8 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!