Submission #1076612


Source Code Expand

Copy
#include<bits/stdc++.h>
 
using namespace std;
 
 
typedef long long int64;
const int mod = 1e9 + 7;
 
struct BinaryIndexedTree
{
  vector< int > data;
 
  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }
 
  int sum(int k)
  {
    int ret = 0;
    for(++k; k > 0; k -= k & -k) (ret += data[k]) %= mod;
    return (ret);
  }
 
  void add(int k, int x)
  {
    for(++k; k < data.size(); k += k & -k) (data[k] += x) %= mod;
  }
 
  int get(int k)
  {
    return ((sum(k) - sum(k - 1) + mod) % mod);
  }
};
 
int main()
{
  int64 N, A, B, X[100000];
  int64 AA[100000], BB[100000];
 
  cin >> N >> A >> B;
  for(int i = 0; i < N; i++) {
    cin >> X[i];
    AA[i] = upper_bound(X, X + i + 1, X[i] - A) - X;
    BB[i] = upper_bound(X, X + i + 1, X[i] - B) - X;
  }
 
  BinaryIndexedTree dp1(N), dp2(N);
  dp1.add(0, 1);
  dp2.add(0, 1);
  int aa = 0, bb = 0;
 
  for(int i = 1; i < N; i++) {
    dp1.add(i, dp2.sum(AA[i]));
    dp2.add(i, dp1.sum(BB[i]));
    if(X[i] - X[i - 1] < A) 
      for(; aa<i; aa++) dp1.add(aa, mod - dp1.get(aa));
    if(X[i] - X[i - 1] < B)
      for(; bb<i; bb++) dp2.add(bb, mod - dp2.get(bb));
  }
 
  cout << (dp1.sum(N - 1) + dp2.sum(N - 1)) % mod << endl;
}

Submission Info

Submission Time
Task C - Division into Two
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1260 Byte
Status
Exec Time 105 ms
Memory 3456 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 0 / 1100 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 105 ms 3328 KB
02.txt 100 ms 3328 KB
03.txt 104 ms 3328 KB
04.txt 104 ms 3328 KB
05.txt 91 ms 3328 KB
06.txt 102 ms 3328 KB
07.txt 105 ms 3328 KB
08.txt 103 ms 3328 KB
09.txt 105 ms 3328 KB
10.txt 105 ms 3328 KB
11.txt 104 ms 3328 KB
12.txt 88 ms 3328 KB
13.txt 104 ms 3328 KB
14.txt 103 ms 3328 KB
15.txt 102 ms 3328 KB
16.txt 54 ms 3328 KB
17.txt 64 ms 3328 KB
18.txt 74 ms 3456 KB
19.txt 78 ms 3328 KB
20.txt 80 ms 3328 KB
21.txt 79 ms 3328 KB
22.txt 77 ms 3328 KB
23.txt 69 ms 3328 KB
24.txt 76 ms 3328 KB
25.txt 95 ms 3328 KB
26.txt 91 ms 3328 KB
27.txt 91 ms 3328 KB
28.txt 92 ms 3328 KB
29.txt 86 ms 3328 KB
30.txt 85 ms 3456 KB
31.txt 84 ms 3328 KB
32.txt 88 ms 3328 KB
33.txt 93 ms 3328 KB
34.txt 75 ms 3328 KB
35.txt 94 ms 3328 KB
36.txt 50 ms 3328 KB
37.txt 58 ms 3328 KB
38.txt 58 ms 3328 KB
39.txt 96 ms 3328 KB
40.txt 67 ms 3328 KB
41.txt 73 ms 3328 KB
42.txt 59 ms 3328 KB
43.txt 88 ms 3328 KB
44.txt 89 ms 3328 KB
45.txt 89 ms 3328 KB
46.txt 88 ms 3328 KB
47.txt 105 ms 3328 KB
48.txt 105 ms 3328 KB
49.txt 2 ms 256 KB
50.txt 2 ms 256 KB
51.txt 2 ms 256 KB
52.txt 2 ms 256 KB
53.txt 2 ms 256 KB
54.txt 2 ms 256 KB
55.txt 2 ms 256 KB
56.txt 2 ms 256 KB
57.txt 2 ms 256 KB
58.txt 2 ms 256 KB
59.txt 2 ms 256 KB
60.txt 2 ms 256 KB
61.txt 2 ms 256 KB
62.txt 2 ms 256 KB
63.txt 2 ms 256 KB
64.txt 2 ms 256 KB
s1.txt 2 ms 256 KB
s2.txt 2 ms 256 KB
s3.txt 2 ms 256 KB
s4.txt 2 ms 256 KB