Submit Info #21166

Problem Lang User Status Time Memory
Static Range Sum java defnotalt RE 1601 ms 91.93 MiB

ケース詳細
Name Status Time Memory
example_00 AC 52 ms 9.00 MiB
max_random_00 AC 1586 ms 91.18 MiB
max_random_01 AC 1601 ms 91.93 MiB
max_random_02 AC 1573 ms 91.06 MiB
max_random_03 AC 1543 ms 91.12 MiB
max_random_04 AC 1574 ms 91.19 MiB
random_00 AC 1335 ms 89.05 MiB
random_01 AC 1396 ms 89.41 MiB
random_02 AC 1164 ms 87.80 MiB
random_03 RE 131 ms 14.44 MiB
random_04 AC 642 ms 33.84 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; } if(q==0) { return; } 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[]) { sort(lft,rgt,indx,0,q-1); 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--; sort(rgt,lft,indx,i,j); 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 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 int partition(int arr[],int brr[],int crr[], int low, int high) { int pivot = arr[high]; // index of smaller element int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; temp = brr[i]; brr[i] = brr[j]; brr[j] = temp; temp = crr[i]; crr[i] = crr[j]; crr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; temp = brr[i + 1]; brr[i + 1] = brr[high]; brr[high] = temp; temp = crr[i + 1]; crr[i + 1] = crr[high]; crr[high] = temp; return i + 1; } /* A[] --> Array to be sorted, l --> Starting index, h --> Ending index */ static void sort(int arr[],int brr[],int crr[], int l, int h) { if(l==h) { return; } // Create an auxiliary stack int[] stack = new int[h - l + 1]; // initialize top of stack int top = -1; // push initial values of l and h to stack stack[++top] = l; stack[++top] = h; // Keep popping from stack while is not empty while (top >= 0) { // Pop h and l h = stack[top--]; l = stack[top--]; // Set pivot element at its correct position // in sorted array int p = partition(arr,brr,crr, l, h); // If there are elements on left side of pivot, // then push left side to stack if (p - 1 > l) { stack[++top] = l; stack[++top] = p - 1; } // If there are elements on right side of pivot, // then push right side to stack if (p + 1 < h) { stack[++top] = p + 1; stack[++top] = h; } } } 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; } }