Submission #1319877


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Mod
{
    static const int P = int(1e9+7);
    int k;

    Mod() = default;
    Mod(const int k) : k(k%P) {}
};

Mod operator+(const Mod a, const Mod b) { return a.k + b.k; }
Mod operator-(const Mod a) { return -a.k + Mod::P; }
Mod& operator+=(Mod& a, const Mod b) { return a = a+b; }

struct FenwickTree
{
    int N;
    vector<Mod> data;
    vector<pair<int, Mod>> modifications;

    FenwickTree(const int N) : N(N), data(N+1) {}

    void add(const int n, const Mod x, const bool track = true)
    {
        if (track) modifications.push_back({n, x});
        for (int i = n+1; i <= N; i += i & -i)
            data[i] += x;
    }

    Mod query(const int n)
    {
        Mod result(0);
        for (int i = n+1; i >= 1; i -= i & -i)
            result += data[i];
        return result;
    }

    void clear()
    {
        for (const auto m : modifications)
            add(m.first, -m.second, false);
        modifications.clear();
    }
};

int main()
{
    int N, A, B; cin >> N >> A >> B;

    vector<ll> S(N+1);
    S[0] = numeric_limits<ll>::min();
    for (int i = 1; i <= N; i++)
        cin >> S[i];

    const auto search = [&](const ll x)
    {
        return int(upper_bound(begin(S), end(S), x) - begin(S)) - 1;
    };

    FenwickTree X(N), Y(N);
    X.add(0, 1); Y.add(0, 1);
    for (int i = 2; i <= N; i++)
    {
        const Mod y = X.query(search(S[i]-B));
        const Mod x = Y.query(search(S[i]-A));

        if (S[i]-S[i-1] < A) X.clear();
        if (S[i]-S[i-1] < B) Y.clear();

        X.add(i-1, x);
        Y.add(i-1, y);
    }
    cout << (X.query(N-1) + Y.query(N-1)).k << endl;
}

Submission Info

Submission Time
Task C - Division into Two
User spencer
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1776 Byte
Status WA
Exec Time 100 ms
Memory 3608 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 4
AC × 41
WA × 27
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 19 ms 2936 KB
02.txt WA 20 ms 2936 KB
03.txt WA 20 ms 2936 KB
04.txt WA 20 ms 2936 KB
05.txt WA 19 ms 2936 KB
06.txt WA 19 ms 2936 KB
07.txt WA 19 ms 2936 KB
08.txt WA 20 ms 2936 KB
09.txt WA 20 ms 2936 KB
10.txt WA 20 ms 2936 KB
11.txt WA 19 ms 2936 KB
12.txt WA 19 ms 2936 KB
13.txt WA 19 ms 2936 KB
14.txt WA 20 ms 2936 KB
15.txt WA 20 ms 2936 KB
16.txt AC 49 ms 2936 KB
17.txt WA 19 ms 1792 KB
18.txt WA 19 ms 2936 KB
19.txt AC 66 ms 1792 KB
20.txt AC 68 ms 1792 KB
21.txt AC 68 ms 1792 KB
22.txt WA 20 ms 1792 KB
23.txt AC 57 ms 1792 KB
24.txt AC 64 ms 1792 KB
25.txt AC 83 ms 1792 KB
26.txt AC 79 ms 1792 KB
27.txt AC 79 ms 1792 KB
28.txt AC 80 ms 1792 KB
29.txt AC 73 ms 1792 KB
30.txt AC 73 ms 1792 KB
31.txt AC 71 ms 1792 KB
32.txt AC 79 ms 1792 KB
33.txt WA 19 ms 1792 KB
34.txt AC 64 ms 1792 KB
35.txt WA 20 ms 2936 KB
36.txt AC 51 ms 3572 KB
37.txt AC 54 ms 2936 KB
38.txt AC 53 ms 2936 KB
39.txt WA 20 ms 2936 KB
40.txt AC 56 ms 1792 KB
41.txt AC 61 ms 1792 KB
42.txt WA 19 ms 2936 KB
43.txt AC 88 ms 3572 KB
44.txt AC 100 ms 3572 KB
45.txt AC 89 ms 3608 KB
46.txt AC 89 ms 3568 KB
47.txt WA 19 ms 2936 KB
48.txt WA 19 ms 2936 KB
49.txt WA 1 ms 256 KB
50.txt AC 1 ms 256 KB
51.txt WA 1 ms 256 KB
52.txt WA 1 ms 256 KB
53.txt AC 1 ms 256 KB
54.txt AC 1 ms 256 KB
55.txt AC 1 ms 256 KB
56.txt AC 1 ms 256 KB
57.txt AC 1 ms 256 KB
58.txt AC 1 ms 256 KB
59.txt AC 1 ms 256 KB
60.txt AC 1 ms 256 KB
61.txt AC 1 ms 256 KB
62.txt AC 1 ms 256 KB
63.txt AC 1 ms 256 KB
64.txt AC 1 ms 256 KB
s1.txt AC 1 ms 256 KB
s2.txt AC 1 ms 256 KB
s3.txt AC 1 ms 256 KB
s4.txt AC 1 ms 256 KB