Submit Info #21179

Problem Lang User Status Time Memory
Static Range Sum java defnotalt AC 1783 ms 95.36 MiB

ケース詳細
Name Status Time Memory
example_00 AC 57 ms 9.12 MiB
max_random_00 AC 1729 ms 92.62 MiB
max_random_01 AC 1718 ms 92.59 MiB
max_random_02 AC 1698 ms 92.48 MiB
max_random_03 AC 1738 ms 92.50 MiB
max_random_04 AC 1783 ms 95.36 MiB
random_00 AC 1480 ms 90.61 MiB
random_01 AC 1517 ms 93.22 MiB
random_02 AC 1333 ms 91.58 MiB
random_03 AC 544 ms 22.13 MiB
random_04 AC 739 ms 37.38 MiB

import java.util.*; import java.io.*; public class Main { static class Scan { private byte[] buf=new byte[1024]; private int index; private InputStream in; private int total; public Scan() { in=System.in; } public int scan()throws IOException { if(total<0) throw new InputMismatchException(); if(index>=total) { index=0; total=in.read(buf); if(total<=0) return -1; } return buf[index++]; } public int scanInt()throws IOException { int integer=0; int n=scan(); while(isWhiteSpace(n)) n=scan(); int neg=1; if(n=='-') { neg=-1; n=scan(); } while(!isWhiteSpace(n)) { if(n>='0'&&n<='9') { integer*=10; integer+=n-'0'; n=scan(); } else throw new InputMismatchException(); } return neg*integer; } public double scanDouble()throws IOException { double doub=0; int n=scan(); while(isWhiteSpace(n)) n=scan(); int neg=1; if(n=='-') { neg=-1; n=scan(); } while(!isWhiteSpace(n)&&n!='.') { if(n>='0'&&n<='9') { doub*=10; doub+=n-'0'; n=scan(); } else throw new InputMismatchException(); } if(n=='.') { n=scan(); double temp=1; while(!isWhiteSpace(n)) { if(n>='0'&&n<='9') { temp/=10; doub+=(n-'0')*temp; n=scan(); } else throw new InputMismatchException(); } } return doub*neg; } public String scanString()throws IOException { StringBuilder sb=new StringBuilder(); int n=scan(); while(isWhiteSpace(n)) n=scan(); while(!isWhiteSpace(n)) { sb.append((char)n); n=scan(); } return sb.toString(); } private boolean isWhiteSpace(int n) { if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1) return true; return false; } } public static void main(String args[]) throws IOException { Scan input=new Scan(); int n=input.scanInt(); int q=input.scanInt(); int arr[]=new int[n]; for(int i=0;i<n;i++) { arr[i]=input.scanInt(); } int lft[]=new int[q]; int rgt[]=new int[q]; int indx[]=new int[q]; for(int i=0;i<q;i++) { lft[i]=input.scanInt(); rgt[i]=input.scanInt()-1; indx[i]=i; } long ans[]=Mos(n,arr,q,lft,rgt,indx); for(int i=0;i<q;i++) { System.out.println(ans[i]); } } public static long[] Mos(int n,int arr[],int q,int lft[],int rgt[],int indx[]) { heapSort(lft,rgt,indx,q); int len=(int)Math.ceil(Math.sqrt(n)); len=Math.max(len,1); int strt=0,end=len-1; for(int i=0;i<q;i++) { int j=i; while(j<q && lft[j]<=end) { j++; } j--; int a[]=new int[j-i+1]; int b[]=new int[j-i+1]; int c[]=new int[j-i+1]; copy(a,rgt,i,j); copy(b,lft,i,j); copy(c,indx,i,j); heapSort(a,b,c,a.length); for(int k=i;k<=j;k++) { rgt[k]=a[k-i]; lft[k]=b[k-i]; indx[k]=c[k-i]; } i=j; strt+=len; end+=len; } long ans[]=new long[q]; long sum=0; int lptr=lft[0],rptr=rgt[0]; for(int i=lft[0];i<=rgt[0];i++) { sum+=arr[i]; } ans[0]=sum; for(int i=1;i<q;i++) { sum=update(arr,lptr,rptr,lft[i],rgt[i],sum); lptr=lft[i]; rptr=rgt[i]; ans[i]=sum; } heapSort(indx,ans,q); return ans; } public static void copy(int arr[],int ori[],int l,int r) { for(int i=l,j=0;i<=r;i++,j++) { arr[j]=ori[i]; } } public static long update(int arr[],int lptr,int rptr,int l,int r,long sum) { if(l>lptr) { for(int i=lptr;i<l;i++) { sum-=arr[i]; } } if(l<lptr) { for(int i=l;i<lptr;i++) { sum+=arr[i]; } } if(r>rptr) { for(int i=rptr+1;i<=r;i++) { sum+=arr[i]; } } if(r<rptr) { for(int i=rptr;i>r;i--) { sum-=arr[i]; } } return sum; } static void buildMaxHeap(int arr[],long brr[], int n) { for (int i = 1; i < n; i++) { // if child is bigger than parent if (arr[i] > arr[(i - 1) / 2]) { int j = i; // swap child and parent until // parent is smaller while (arr[j] > arr[(j - 1) / 2]) { swap(arr, j, (j - 1) / 2); swap(brr, j, (j - 1) / 2); j = (j - 1) / 2; } } } } static void heapSort(int arr[],long brr[], int n) { buildMaxHeap(arr, brr,n); for (int i = n - 1; i > 0; i--) { // swap value of first indexed // with last indexed swap(arr, 0, i); swap(brr, 0, i); // maintaining heap property // after each swapping int j = 0, index; do { index = (2 * j + 1); // if left child is smaller than // right child point index variable // to right child if (index < (i - 1) && arr[index] < arr[index + 1]) index++; // if parent is smaller than child // then swapping parent with child // having higher value if (index < i && arr[j] < arr[index]) { swap(arr, j, index); swap(brr, j, index); } j = index; } while (index < i); } } public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i]=a[j]; a[j] = temp; } public static void swap(long[] a, int i, int j) { long temp = a[i]; a[i]=a[j]; a[j] = temp; } static void buildMaxHeap(int arr[],int brr[],int crr[], int n) { for (int i = 1; i < n; i++) { // if child is bigger than parent if (arr[i] > arr[(i - 1) / 2]) { int j = i; // swap child and parent until // parent is smaller while (arr[j] > arr[(j - 1) / 2]) { swap(arr, j, (j - 1) / 2); swap(brr, j, (j - 1) / 2); swap(crr, j, (j - 1) / 2); j = (j - 1) / 2; } } } } static void heapSort(int arr[],int brr[],int crr[], int n) { buildMaxHeap(arr, brr,crr,n); for (int i = n - 1; i > 0; i--) { // swap value of first indexed // with last indexed swap(arr, 0, i); swap(brr, 0, i); swap(crr, 0, i); // maintaining heap property // after each swapping int j = 0, index; do { index = (2 * j + 1); // if left child is smaller than // right child point index variable // to right child if (index < (i - 1) && arr[index] < arr[index + 1]) index++; // if parent is smaller than child // then swapping parent with child // having higher value if (index < i && arr[j] < arr[index]) { swap(arr, j, index); swap(brr, j, index); swap(crr, j, index); } j = index; } while (index < i); } } }