fork download
copy 
  1.  
  2.  
  3. import java.util.*;
  4.  
  5. import java.util.regex.*;
  6. import static java.lang.Math.*;
  7. import static java.util.Arrays.*;
  8. import static java.lang.Integer.*;
  9. import static java.lang.Double.*;
  10. import static java.util.Collections.*;
  11. import java.io.*;
  12.  
  13. public class _C {
  14.  
  15.     public void solve() {
  16. 		int N = in.nextInt();
  17. //		int N = 200000;
  18. 		int Q = in.nextInt();
  19. //		int Q = 200000;
  20. 		int [] a=new int[N];
  21. 		for (int i = 0; i < a.length; i++) {
  22. 			a[i]=in.nextInt();
  23. //			a[i]=i+;
  24. 		}
  25. 		T = new long[N*4];
  26. 		lp = new long[N*4];
  27. 		a2=new long[N];
  28. 		for (int i = 0; i < Q; i++) {
  29. 			int l=in.nextInt()-1;
  30. 			int r=in.nextInt()-1;
  31. //			int l = i;
  32. //			int r=i+1;
  33. //			print(l,r);
  34. 			update(1,0,N-1,l,r);
  35. 		}
  36. //		int xx = 40000000000;
  37. 		query(1,0,N-1);
  38. 		sort(a);
  39. 		sort(a2);
  40. 		long r=0;
  41. 		for (int i = 0; i < a.length; i++) {
  42. 			r+=((long)a[i])*a2[i];
  43. 		}
  44. 		System.out.println(r);
  45. //		print(a,a2);
  46. 	}
  47. 	long a2[];
  48. 	long[]T;
  49. 	long[]lp;
  50. 	void query(int node, int a, int b){
  51. 		push(node, a, b);
  52. 		if(a==b){
  53. 			a2[b]=T[node];
  54. 			return;
  55. 		}
  56. 		int l=node*2,r=l+1,mid=(a+b)>>1;
  57. 		query(l,a,mid);
  58. 		query(r,mid+1,b);
  59. //		T[node]=T[l]+T[r];
  60. 	}
  61. 	void push(int node , int a, int b){
  62. 		if(lp[node]>0){
  63. 			int l=node*2,r=l+1;
  64. 			if(a!=b){
  65. 				lp[l]+=lp[node];
  66. 				lp[r]+=lp[node];
  67. 			}
  68. 			T[node]+=lp[node];
  69. 			lp[node]=0;
  70. 		}
  71. 	}
  72.  
  73. 	void update(int node, int a, int b, int i, int j){
  74.  
  75. 		if(a>b || i>b || a>j)
  76. 			return;
  77.  
  78. //		print(node, a, b, mid, i, j);
  79. //		push(node, a, b);
  80.  
  81. 		if(a>=i && b<=j){
  82. 			lp[node]++;
  83. //			push(node, a, b);
  84. 			return;
  85. 		}
  86. 		int l=node*2,r=l+1,mid=(a+b)>>1;
  87. 		update(l,a,mid,i,j);
  88. 		update(r,mid+1,b,i,j);
  89. //		T[node]=T[l]+T[r];
  90. 	}
  91. 	_C(){
  92. 		in = new Scanner(System.in);
  93. 		out = new PrintWriter(System.out);
  94. 	}
  95. 	public static void close(){
  96. 		in.close();
  97. 		out.close();
  98. 	}
  99. 	public static void main(String[] args) throws Exception {
  100. 		new _C().solve();
  101. 		close();
  102. 	}
  103.  
  104. 	static Scanner in;
  105. 	static PrintWriter out;
  106.  
  107. 	static int readInt(){
  108. 		return in.nextInt();
  109. //		return parseInt(in.nextLine());
  110. 	}
  111. 	static int[] readIntArray(){
  112. 		String l[] = in.next().split(" ");
  113. 		int[] r=new int[l.length];
  114. 		for (int i = 0; i < l.length; i++) {
  115. 			r[i]=parseInt(l[i]);
  116. 		}
  117. 		return r;
  118. 	}
  119.  
  120. 	static void print(Object... ob) {
  121. 		System.out.println(Arrays.deepToString(ob).replace("],", "],\n"));
  122. 	}
  123. }
  124.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:13: error: class _C is public, should be declared in a file named _C.java
public class _C {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/wkFEuE
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
secret

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!