답안 #343906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343906	2021-01-04T17:48:08 Z	KWang31	Money (IZhO17_money)	Java 11	100 / 100	506 ms	46944 KB

money

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[i])){
              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
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	12524 KB	Output is correct
2	Correct	75 ms	12508 KB	Output is correct
3	Correct	73 ms	12396 KB	Output is correct
4	Correct	73 ms	12508 KB	Output is correct
5	Correct	72 ms	12396 KB	Output is correct
6	Correct	72 ms	12380 KB	Output is correct
7	Correct	76 ms	12524 KB	Output is correct
8	Correct	72 ms	12416 KB	Output is correct
9	Correct	74 ms	12396 KB	Output is correct
10	Correct	72 ms	12396 KB	Output is correct
11	Correct	73 ms	12524 KB	Output is correct
12	Correct	75 ms	12396 KB	Output is correct
13	Correct	72 ms	12396 KB	Output is correct
14	Correct	73 ms	12416 KB	Output is correct
15	Correct	73 ms	12396 KB	Output is correct
16	Correct	75 ms	12396 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	12524 KB	Output is correct
2	Correct	75 ms	12508 KB	Output is correct
3	Correct	73 ms	12396 KB	Output is correct
4	Correct	73 ms	12508 KB	Output is correct
5	Correct	72 ms	12396 KB	Output is correct
6	Correct	72 ms	12380 KB	Output is correct
7	Correct	76 ms	12524 KB	Output is correct
8	Correct	72 ms	12416 KB	Output is correct
9	Correct	74 ms	12396 KB	Output is correct
10	Correct	72 ms	12396 KB	Output is correct
11	Correct	73 ms	12524 KB	Output is correct
12	Correct	75 ms	12396 KB	Output is correct
13	Correct	72 ms	12396 KB	Output is correct
14	Correct	73 ms	12416 KB	Output is correct
15	Correct	73 ms	12396 KB	Output is correct
16	Correct	75 ms	12396 KB	Output is correct
17	Correct	74 ms	12524 KB	Output is correct
18	Correct	73 ms	12524 KB	Output is correct
19	Correct	77 ms	12444 KB	Output is correct
20	Correct	72 ms	12524 KB	Output is correct
21	Correct	75 ms	12652 KB	Output is correct
22	Correct	76 ms	12524 KB	Output is correct
23	Correct	74 ms	12380 KB	Output is correct
24	Correct	74 ms	12524 KB	Output is correct
25	Correct	73 ms	12524 KB	Output is correct
26	Correct	73 ms	12524 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	12524 KB	Output is correct
2	Correct	75 ms	12508 KB	Output is correct
3	Correct	73 ms	12396 KB	Output is correct
4	Correct	73 ms	12508 KB	Output is correct
5	Correct	72 ms	12396 KB	Output is correct
6	Correct	72 ms	12380 KB	Output is correct
7	Correct	76 ms	12524 KB	Output is correct
8	Correct	72 ms	12416 KB	Output is correct
9	Correct	74 ms	12396 KB	Output is correct
10	Correct	72 ms	12396 KB	Output is correct
11	Correct	73 ms	12524 KB	Output is correct
12	Correct	75 ms	12396 KB	Output is correct
13	Correct	72 ms	12396 KB	Output is correct
14	Correct	73 ms	12416 KB	Output is correct
15	Correct	73 ms	12396 KB	Output is correct
16	Correct	75 ms	12396 KB	Output is correct
17	Correct	74 ms	12524 KB	Output is correct
18	Correct	73 ms	12524 KB	Output is correct
19	Correct	77 ms	12444 KB	Output is correct
20	Correct	72 ms	12524 KB	Output is correct
21	Correct	75 ms	12652 KB	Output is correct
22	Correct	76 ms	12524 KB	Output is correct
23	Correct	74 ms	12380 KB	Output is correct
24	Correct	74 ms	12524 KB	Output is correct
25	Correct	73 ms	12524 KB	Output is correct
26	Correct	73 ms	12524 KB	Output is correct
27	Correct	76 ms	12316 KB	Output is correct
28	Correct	76 ms	12524 KB	Output is correct
29	Correct	77 ms	12524 KB	Output is correct
30	Correct	78 ms	12524 KB	Output is correct
31	Correct	75 ms	12524 KB	Output is correct
32	Correct	77 ms	12524 KB	Output is correct
33	Correct	77 ms	12524 KB	Output is correct
34	Correct	78 ms	12488 KB	Output is correct
35	Correct	78 ms	12512 KB	Output is correct
36	Correct	81 ms	12652 KB	Output is correct
37	Correct	80 ms	12508 KB	Output is correct
38	Correct	78 ms	12368 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	12524 KB	Output is correct
2	Correct	75 ms	12508 KB	Output is correct
3	Correct	73 ms	12396 KB	Output is correct
4	Correct	73 ms	12508 KB	Output is correct
5	Correct	72 ms	12396 KB	Output is correct
6	Correct	72 ms	12380 KB	Output is correct
7	Correct	76 ms	12524 KB	Output is correct
8	Correct	72 ms	12416 KB	Output is correct
9	Correct	74 ms	12396 KB	Output is correct
10	Correct	72 ms	12396 KB	Output is correct
11	Correct	73 ms	12524 KB	Output is correct
12	Correct	75 ms	12396 KB	Output is correct
13	Correct	72 ms	12396 KB	Output is correct
14	Correct	73 ms	12416 KB	Output is correct
15	Correct	73 ms	12396 KB	Output is correct
16	Correct	75 ms	12396 KB	Output is correct
17	Correct	74 ms	12524 KB	Output is correct
18	Correct	73 ms	12524 KB	Output is correct
19	Correct	77 ms	12444 KB	Output is correct
20	Correct	72 ms	12524 KB	Output is correct
21	Correct	75 ms	12652 KB	Output is correct
22	Correct	76 ms	12524 KB	Output is correct
23	Correct	74 ms	12380 KB	Output is correct
24	Correct	74 ms	12524 KB	Output is correct
25	Correct	73 ms	12524 KB	Output is correct
26	Correct	73 ms	12524 KB	Output is correct
27	Correct	76 ms	12316 KB	Output is correct
28	Correct	76 ms	12524 KB	Output is correct
29	Correct	77 ms	12524 KB	Output is correct
30	Correct	78 ms	12524 KB	Output is correct
31	Correct	75 ms	12524 KB	Output is correct
32	Correct	77 ms	12524 KB	Output is correct
33	Correct	77 ms	12524 KB	Output is correct
34	Correct	78 ms	12488 KB	Output is correct
35	Correct	78 ms	12512 KB	Output is correct
36	Correct	81 ms	12652 KB	Output is correct
37	Correct	80 ms	12508 KB	Output is correct
38	Correct	78 ms	12368 KB	Output is correct
39	Correct	363 ms	29116 KB	Output is correct
40	Correct	421 ms	43856 KB	Output is correct
41	Correct	344 ms	28768 KB	Output is correct
42	Correct	342 ms	28000 KB	Output is correct
43	Correct	320 ms	22868 KB	Output is correct
44	Correct	454 ms	46560 KB	Output is correct
45	Correct	459 ms	46560 KB	Output is correct
46	Correct	485 ms	46732 KB	Output is correct
47	Correct	444 ms	46944 KB	Output is correct
48	Correct	506 ms	46804 KB	Output is correct
49	Correct	472 ms	46816 KB	Output is correct
50	Correct	486 ms	46632 KB	Output is correct
51	Correct	494 ms	46564 KB	Output is correct
52	Correct	479 ms	46752 KB	Output is correct
53	Correct	491 ms	46808 KB	Output is correct
54	Correct	479 ms	46532 KB	Output is correct
55	Correct	473 ms	46676 KB	Output is correct
56	Correct	469 ms	46032 KB	Output is correct
57	Correct	485 ms	45920 KB	Output is correct
58	Correct	476 ms	45684 KB	Output is correct
59	Correct	480 ms	45920 KB	Output is correct
60	Correct	475 ms	45940 KB	Output is correct
61	Correct	473 ms	46144 KB	Output is correct
62	Correct	469 ms	45792 KB	Output is correct

답안 #343906

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 20.0 / 20.0

Subtask #4 55.0 / 55.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
20.0 / 20.0

Subtask #4
55.0 / 55.0