Submission #2152681


Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

class BIT{
    int N;
    long[] data;
    long inf = 1000000007;
    
    public BIT(int n){
        N = n;
        data = new long[N+1];
        Arrays.fill(data,0);
    }

    public void add(int pos,long dat){
        for(int x = pos;x<=N; x += x&-x)data[x] = (data[x]+dat)%inf;
    }

    public long getSum(int pos){
        if(pos==0)return 0;
        long res = 0;
        for(int x = pos; x>0;x-=x&-x)res=(res+data[x])%inf;
        return res;
    }

}



class Main{

    static long A,B;
    static int N;
    static long[] S;
    static int findIndex(long s){
        int left=0;
        int right=N+1;
        while(right-left>1){
            int center = (left+right)/2;
            if(s-S[center] >=B)left=center;
            else right=center;
        }
        return left;
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        A = scan.nextLong();
        B = scan.nextLong();
        S = new long[N+1];
        S[0]=Long.MIN_VALUE/3;
        for(int i=0;i<N;++i)S[i+1] = scan.nextLong();
        if(A>B){
            long a = A;
            A=B;
            B=a;
        }
        for(int i=0;i<N-1;++i)if(S[i+2]-S[i] < A){
                System.out.println(0);
                return;
        }
        long mod = (long)1e9+7;
        //1-index
        BIT bit = new BIT(N+1);
        bit.add(1, 1);
        bit.add(2,1);
        int leftindex = 0;
        for(int i=2;i<=N;++i){
            long delta = S[i]-S[i-1];
            if(delta < A){
                bit.add(i+1, (bit.getSum(findIndex(S[i])+1) - bit.getSum(leftindex)+mod)%mod);
                leftindex = i-1;
            }
            else if(delta < B){
                bit.add(i+1, (bit.getSum(findIndex(S[i])+1) - bit.getSum(leftindex)+mod)%mod);
            }
            else bit.add(i+1, (bit.getSum(i+1) - bit.getSum(leftindex) + mod)%mod);
        }
        System.out.println(leftindex);
        System.out.println((bit.getSum(N+1) - bit.getSum(leftindex)+mod)%mod);
    }
}

Submission Info

Submission Time
Task C - Division into Two
User inmir
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 2182 Byte
Status WA
Exec Time 598 ms
Memory 59268 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 1
WA × 3
AC × 10
WA × 58
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt, s4.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt WA 514 ms 48808 KB
02.txt WA 545 ms 48932 KB
03.txt WA 525 ms 46884 KB
04.txt WA 548 ms 46152 KB
05.txt WA 511 ms 53740 KB
06.txt WA 545 ms 49448 KB
07.txt WA 536 ms 47172 KB
08.txt WA 511 ms 51292 KB
09.txt WA 501 ms 48144 KB
10.txt WA 482 ms 51604 KB
11.txt WA 543 ms 58796 KB
12.txt WA 526 ms 49204 KB
13.txt WA 598 ms 53088 KB
14.txt WA 521 ms 46784 KB
15.txt WA 548 ms 48572 KB
16.txt WA 456 ms 44928 KB
17.txt WA 523 ms 48888 KB
18.txt WA 542 ms 50568 KB
19.txt WA 513 ms 48380 KB
20.txt WA 536 ms 47384 KB
21.txt WA 537 ms 48644 KB
22.txt WA 513 ms 48976 KB
23.txt WA 447 ms 49892 KB
24.txt WA 488 ms 46540 KB
25.txt WA 555 ms 53024 KB
26.txt WA 531 ms 46292 KB
27.txt WA 564 ms 49044 KB
28.txt WA 560 ms 49080 KB
29.txt WA 564 ms 50408 KB
30.txt WA 565 ms 46632 KB
31.txt WA 563 ms 47264 KB
32.txt WA 562 ms 45944 KB
33.txt WA 565 ms 50564 KB
34.txt WA 501 ms 47380 KB
35.txt WA 550 ms 47760 KB
36.txt WA 462 ms 49360 KB
37.txt WA 491 ms 50804 KB
38.txt WA 482 ms 50488 KB
39.txt WA 527 ms 44560 KB
40.txt WA 460 ms 50424 KB
41.txt WA 513 ms 51048 KB
42.txt AC 421 ms 47644 KB
43.txt WA 479 ms 50016 KB
44.txt WA 512 ms 49428 KB
45.txt WA 507 ms 46816 KB
46.txt WA 527 ms 51192 KB
47.txt AC 494 ms 52856 KB
48.txt AC 487 ms 59268 KB
49.txt WA 92 ms 19796 KB
50.txt WA 91 ms 19924 KB
51.txt WA 93 ms 21716 KB
52.txt AC 91 ms 18640 KB
53.txt WA 92 ms 19412 KB
54.txt WA 92 ms 18900 KB
55.txt WA 92 ms 19028 KB
56.txt WA 92 ms 21460 KB
57.txt AC 92 ms 18900 KB
58.txt AC 91 ms 18772 KB
59.txt AC 91 ms 18644 KB
60.txt WA 91 ms 20564 KB
61.txt WA 90 ms 19796 KB
62.txt AC 93 ms 19540 KB
63.txt AC 92 ms 16852 KB
64.txt WA 93 ms 19668 KB
s1.txt WA 92 ms 22740 KB
s2.txt WA 93 ms 18388 KB
s3.txt WA 93 ms 21716 KB
s4.txt AC 92 ms 20692 KB