G2A Many GEOs
SHARE
TWEET

Untitled

a guest Feb 24th, 2013 509 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
Ledger Nano X - The secure hardware wallet
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