Advertisement
Guest User

Untitled

a guest
Feb 24th, 2013
1,509
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.73 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement