oj.uz

Submission #343900

# Submission time Handle Problem Language Result Execution time Memory
343900 2021-01-04T17:40:26 Z KWang31 Money (IZhO17_money) Java 11
0 / 100
 84 ms 12664 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 79 ms 12652 KB Output is correct
2 Correct 74 ms 12524 KB Output is correct
3 Correct 77 ms 12396 KB Output is correct
4 Correct 73 ms 12524 KB Output is correct
5 Correct 79 ms 12524 KB Output is correct
6 Correct 80 ms 12444 KB Output is correct
7 Correct 79 ms 12416 KB Output is correct
8 Correct 79 ms 12516 KB Output is correct
9 Correct 74 ms 12540 KB Output is correct
10 Correct 73 ms 12396 KB Output is correct
11 Correct 84 ms 12664 KB Output is correct
12 Incorrect 76 ms 12396 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 12652 KB Output is correct
2 Correct 74 ms 12524 KB Output is correct
3 Correct 77 ms 12396 KB Output is correct
4 Correct 73 ms 12524 KB Output is correct
5 Correct 79 ms 12524 KB Output is correct
6 Correct 80 ms 12444 KB Output is correct
7 Correct 79 ms 12416 KB Output is correct
8 Correct 79 ms 12516 KB Output is correct
9 Correct 74 ms 12540 KB Output is correct
10 Correct 73 ms 12396 KB Output is correct
11 Correct 84 ms 12664 KB Output is correct
12 Incorrect 76 ms 12396 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 12652 KB Output is correct
2 Correct 74 ms 12524 KB Output is correct
3 Correct 77 ms 12396 KB Output is correct
4 Correct 73 ms 12524 KB Output is correct
5 Correct 79 ms 12524 KB Output is correct
6 Correct 80 ms 12444 KB Output is correct
7 Correct 79 ms 12416 KB Output is correct
8 Correct 79 ms 12516 KB Output is correct
9 Correct 74 ms 12540 KB Output is correct
10 Correct 73 ms 12396 KB Output is correct
11 Correct 84 ms 12664 KB Output is correct
12 Incorrect 76 ms 12396 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 12652 KB Output is correct
2 Correct 74 ms 12524 KB Output is correct
3 Correct 77 ms 12396 KB Output is correct
4 Correct 73 ms 12524 KB Output is correct
5 Correct 79 ms 12524 KB Output is correct
6 Correct 80 ms 12444 KB Output is correct
7 Correct 79 ms 12416 KB Output is correct
8 Correct 79 ms 12516 KB Output is correct
9 Correct 74 ms 12540 KB Output is correct
10 Correct 73 ms 12396 KB Output is correct
11 Correct 84 ms 12664 KB Output is correct
12 Incorrect 76 ms 12396 KB Output isn't correct
13 Halted 0 ms 0 KB -