fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. #define gc getchar
  8.  
  9. inline int geti(){
  10.   register int c = gc(), x = 0;
  11.   for(; c<'0' || c>'9'; c=gc());
  12.   for(; c>='0' && c<='9'; c=gc())
  13.     x = (x<<1) + (x<<3) + c -'0';
  14.   return x;
  15. }
  16.  
  17. const int MAXN = 2e5 + 5, MAXA = 1e6 + 5, SQRT = 500;
  18.  
  19. int A[MAXN], K[MAXA], pos[MAXN], L[MAXN], R[MAXN], N, Q, ll, rr;
  20. unsigned long long sum, res[MAXN];
  21.  
  22. bool comp(int i, int j){
  23.   if(L[i] / SQRT != L[j] / SQRT) return L[i] < L[j];
  24.   return R[i] < R[j];
  25. }
  26.  
  27. void Delete(int x){
  28.   int &k = K[A[x]];
  29.   sum -= 1LLU * k * k * A[x];
  30.   k--;
  31.   sum += 1LLU * k * k * A[x];
  32. }
  33.  
  34. void Insert(int x){
  35.   int &k = K[A[x]];
  36.   sum -= 1LLU * k * k * A[x];
  37.   k++;
  38.   sum += 1LLU * k * k * A[x];
  39. }
  40.  
  41. int main(){
  42.   N = geti(), Q = geti();
  43.   for(int i=1; i<=N; ++i) A[i] = geti();
  44.   for(int i=1; i<=Q; ++i) pos[i] = i, L[i] = geti(), R[i] = geti(); 
  45.   sort(pos + 1, pos + Q + 1, comp);
  46.   ll = 1;
  47.   for(int i=1; i<=Q; ++i){
  48.     int l = L[pos[i]], r = R[pos[i]];
  49.     while(ll < l) Delete(ll++);
  50.     while(ll > l) Insert(--ll);
  51.     while(rr < r) Insert(++rr);
  52.     while(rr > r) Delete(rr--);
  53.     res[pos[i]] = sum;
  54.   }
  55.   for(int i=1; i<=Q; ++i) printf("%I64d\n", res[i]);
  56.   return 0;
  57. }
Time limit exceeded #stdin #stdout 5s 12064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hBVnIb
language:
C++14 (gcc 8.3)
created:
7 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!