oj.uz

Submission #343901

# Submission time Handle Problem Language Result Execution time Memory
343901 2021-01-04T17:40:51 Z KWang31 Money (IZhO17_money) Java 11
0 / 100
 78 ms 12524 KB 
import java.io.*; import java.util.*;
public class money{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=998244353;
    static int[] tree; static int MAXN=1000001;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int[] a=new int[N];
        for(int i=0;i<N;i++){
          a[i]=br.nextInt();
        }
        tree=new int[MAXN];
        int ans=0; int ii;
        for(int i=0; i<N; i++){
           ii=i+1; ans++;
           while(ii<N && a[ii]>=a[ii-1] && sum(a[ii]-1)==sum(a[ii-1])){
              ii++;
           }
           for(int j=i;j<ii; j++){
             upd(a[j]);
           }
          //The segment [i,ii-1] can be used
          i=ii-1;
        }
      System.out.println(ans);
    }
     //tree[i]=sum(i-2^{\nu_2(i)}+1,i)
    public static int sum(int i){//This is a consequence of unique expression in base 2
        int ans=0;
        while(i>0){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    public static void upd(int i){//Increment arr[i] by k
        while(i<MAXN){
            tree[i]++;
            i+=(i&-i);// Note (k&-k) is the largest power of 2 dividing k
            //These intervals all contain i
        }
    }
    
  
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12524 KB Output is correct
2 Correct 74 ms 12368 KB Output is correct
3 Correct 78 ms 12396 KB Output is correct
4 Correct 74 ms 12396 KB Output is correct
5 Correct 72 ms 12396 KB Output is correct
6 Correct 74 ms 12496 KB Output is correct
7 Correct 75 ms 12392 KB Output is correct
8 Incorrect 76 ms 12268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12524 KB Output is correct
2 Correct 74 ms 12368 KB Output is correct
3 Correct 78 ms 12396 KB Output is correct
4 Correct 74 ms 12396 KB Output is correct
5 Correct 72 ms 12396 KB Output is correct
6 Correct 74 ms 12496 KB Output is correct
7 Correct 75 ms 12392 KB Output is correct
8 Incorrect 76 ms 12268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12524 KB Output is correct
2 Correct 74 ms 12368 KB Output is correct
3 Correct 78 ms 12396 KB Output is correct
4 Correct 74 ms 12396 KB Output is correct
5 Correct 72 ms 12396 KB Output is correct
6 Correct 74 ms 12496 KB Output is correct
7 Correct 75 ms 12392 KB Output is correct
8 Incorrect 76 ms 12268 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 12524 KB Output is correct
2 Correct 74 ms 12368 KB Output is correct
3 Correct 78 ms 12396 KB Output is correct
4 Correct 74 ms 12396 KB Output is correct
5 Correct 72 ms 12396 KB Output is correct
6 Correct 74 ms 12496 KB Output is correct
7 Correct 75 ms 12392 KB Output is correct
8 Incorrect 76 ms 12268 KB Output isn't correct
9 Halted 0 ms 0 KB -