daily pastebin goal
77%
SHARE
TWEET

Untitled

a guest Feb 24th, 2013 371 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.InputStreamReader;
  5. import java.util.Arrays;
  6. import java.util.Random;
  7. import java.util.StringTokenizer;
  8. public class C {
  9.         static void shuffle(int[] a)
  10.         {
  11.                 int n=a.length;
  12.                 Random rnd = new Random(System.nanoTime());
  13.                 for (int i=0; i<n; ++i)
  14.                 {
  15.                         int v=rnd.nextInt(n-i);
  16.                         int tmp=a[i+v];
  17.                         a[i+v]=a[i];
  18.                         a[i]=tmp;
  19.                 }
  20.         }
  21.         public static void main(String[] args) throws Exception {
  22.                 InputReader in = new InputReader(System.in);
  23.                 int n=in.nextInt();
  24.                 int q=in.nextInt();
  25.                 int a[]= new int [n];
  26.                 int b[]=new int[n];
  27.                 for (int i=0; i<n; ++i)
  28.                         a[i]=in.nextInt();
  29.                 for (int i=0; i<q; ++i)
  30.                 {
  31.                         int l=in.nextInt();
  32.                         int r=in.nextInt();
  33.                         l--;
  34.                         r--;
  35.                         b[l]++;
  36.                         if (r<n-1)
  37.                                 b[r+1]--;
  38.                 }
  39.                 int v=0;
  40.                 shuffle(a);
  41.                 Arrays.sort(a);
  42.                 int val[] = new int[n];
  43.                 for (int i=0; i<n; ++i)
  44.                 {
  45.                         v+=b[i];
  46.                         val[i]=v;
  47.                 }
  48.                 shuffle(val);
  49.                 Arrays.sort(val);
  50.                 long res=0;
  51.                 for (int i=0; i<n; ++i)
  52.                 {
  53.                         long c=a[i];
  54.                         c*=val[i];
  55.                         res+=c;
  56.                 }
  57.                 System.out.println(res);
  58.         }
  59. }
  60.  
  61.  
  62. class InputReader {
  63.         BufferedReader reader;
  64.         StringTokenizer tokenizer;
  65.  
  66.         public InputReader(InputStream stream) {
  67.                 reader = new BufferedReader(new InputStreamReader(stream));
  68.                 tokenizer = null;
  69.         }
  70.  
  71.         public String next() {
  72.                 while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  73.                         try {
  74.                                 tokenizer = new StringTokenizer(reader.readLine());
  75.                         } catch (IOException e) {
  76.                                 throw new RuntimeException(e);
  77.                         }
  78.                 }
  79.                 return tokenizer.nextToken();
  80.         }
  81.  
  82.         public long nextLong() {
  83.                 return Long.parseLong(next());
  84.         }
  85.         public int nextInt() {
  86.                 return Integer.parseInt(next());
  87.         }
  88.  
  89. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top