제출 #110768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110768		TAISA_	Boat (APIO16_boat)	C++14	31 / 100	541 ms	78036 KiB

boat

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42