oj.uz

Submission #110768

# Submission time Handle Problem Language Result Execution time Memory
110768 2019-05-12T08:01:35 Z TAISA_ Boat (APIO16_boat) C++14
31 / 100
 541 ms 78036 KB 
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 40) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
struct BIT {
    vector<ll> bit;
    BIT(int n) { bit.resize(++n, 0); }
    void add(int k, ll x) {
        for(++k; k < bit.size(); k += k & -k) {
            bit[k] += x;
            bit[k] %= MOD;
        }
    }
    ll sum(int k) {
        ll res = 0;
        for(++k; k > 0; k -= k & -k) {
            res += bit[k];
            res %= MOD;
        }
        return res;
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n), b(n), v;
    ll s = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        s += b[i] - a[i];
    }
    if(s > 1000000) {
        return 0;
    }
    for(int i = 0; i < n; i++) {
        for(int j = a[i]; j <= b[i]; j++) {
            v.push_back(j);
        }
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    map<ll, int> mp;
    for(int i = 0; i < v.size(); i++) {
        mp[v[i]] = i + 1;
    }
    BIT bit(v.size() + 10);
    bit.add(0, 1);
    for(int i = 0; i < n; i++) {
        int s = mp[a[i]], t = mp[b[i]];
        for(int j = t; j >= s; j--) {
            bit.add(j, bit.sum(j - 1));
        }
    }
    ll res = bit.sum(v.size()) - 1LL + MOD;
    res %= MOD;
    cout << res << endl;
}

Compilation message

boat.cpp: In member function 'void BIT::add(int, ll)':
boat.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(++k; k < bit.size(); k += k & -k) {
                  ~~^~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); i++) {
                    ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 90 ms 8752 KB Output is correct
22 Correct 83 ms 8688 KB Output is correct
23 Correct 81 ms 8688 KB Output is correct
24 Correct 83 ms 8688 KB Output is correct
25 Correct 82 ms 8688 KB Output is correct
26 Correct 90 ms 8688 KB Output is correct
27 Correct 90 ms 8688 KB Output is correct
28 Correct 89 ms 8688 KB Output is correct
29 Correct 94 ms 8716 KB Output is correct
30 Correct 499 ms 78036 KB Output is correct
31 Correct 478 ms 76540 KB Output is correct
32 Correct 472 ms 77912 KB Output is correct
33 Correct 474 ms 75988 KB Output is correct
34 Correct 472 ms 76672 KB Output is correct
35 Correct 488 ms 73048 KB Output is correct
36 Correct 525 ms 75516 KB Output is correct
37 Correct 505 ms 76384 KB Output is correct
38 Correct 541 ms 73908 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 90 ms 8752 KB Output is correct
22 Correct 83 ms 8688 KB Output is correct
23 Correct 81 ms 8688 KB Output is correct
24 Correct 83 ms 8688 KB Output is correct
25 Correct 82 ms 8688 KB Output is correct
26 Correct 90 ms 8688 KB Output is correct
27 Correct 90 ms 8688 KB Output is correct
28 Correct 89 ms 8688 KB Output is correct
29 Correct 94 ms 8716 KB Output is correct
30 Correct 499 ms 78036 KB Output is correct
31 Correct 478 ms 76540 KB Output is correct
32 Correct 472 ms 77912 KB Output is correct
33 Correct 474 ms 75988 KB Output is correct
34 Correct 472 ms 76672 KB Output is correct
35 Correct 488 ms 73048 KB Output is correct
36 Correct 525 ms 75516 KB Output is correct
37 Correct 505 ms 76384 KB Output is correct
38 Correct 541 ms 73908 KB Output is correct
39 Incorrect 3 ms 260 KB Output isn't correct
40 Halted 0 ms 0 KB -