oj.uz

Submission #107006

# Submission time Handle Problem Language Result Execution time Memory
107006 2019-04-21T12:45:57 Z golub Boat (APIO16_boat) C++14
0 / 100
 2000 ms 277588 KB 
// #define TASK "sweets"

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse4.2,avx2")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("unroll-all-loops")

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>

// using namespace __gnu_cxx;`
// using namespace __gnu_pbds;
using namespace std;

// template<class K>
// using ordered_set = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

// template<class K, class T>
// using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 rnd((int)chrono::high_resolution_clock::now().time_since_epoch().count());
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
#define len(x) (long long)x.size()
#define int long long

typedef long long ll;
typedef long double ld;

const long long INF = (int)numeric_limits<int>::max() >> 1;
const long long MAXN = (long long)1e5 + 10;
const long long MOD = (long long)1e9 + 7;
const long double EPS = (long double)1e-12;

// char _buf_[(int)6e6];
// size_t _p_ = 0;

// inline void *operator new(size_t _n_) {
//    _p_ += _n_;
//    return _buf_ + _p_ - _n_;
// }
// inline void operator delete(void*) {};

ll power(ll x, ll n, ll mod = 1e9 + 7) {
    if (n == 0) return 1ll;
    if (n & 1ll) return power(x, n - 1ll, mod) * x % mod;
    ll tmp = power(x, n >> 1ll, mod);
    return (tmp * tmp) % mod;
}

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd (b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

template<typename A, typename B>
bool cmax(A &a, const B &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<typename A, typename B>
bool cmin(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int mod(int x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}

struct FT {
    unordered_map<int, int> d;
    int MAXN = 1e9 + 1;

    void update(int k, int value) {
        for (int i = k; i < MAXN; i |= (i + 1)) {
            d[i] = mod(d[i] + value);
        }
    }

    int query(int k) {
        int S = 0;
        for (int i = k; i >= 0; i = (i & (i + 1)) - 1) {
            auto it = d.find(i);
            if (it != d.end())
                S = mod(S + (*it).S);
        }
        return S;
    }

    int query(int l, int r) {
        return mod(query(r) - query(l - 1));
    }
};

signed main() {
#ifndef LOCAL
    #ifdef TASK
    freopen(TASK".in", "r", stdin);
    freopen(TASK".out", "w", stdout);
#endif
#endif
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // == SOLUTION == //
    int n;
    cin >> n;
    vector<pii> a;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a.pb({l, r});
    }
    FT T;
    vector<map<int, int>> dp(n);
    for (int i = 0; i < n; i++) {
        for (int j = a[i].F; j <= a[i].S; j++) {
            dp[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = a[i].F; j <= a[i].S; j++) {
            dp[i][j] = mod(dp[i][j] + T.query(j));
        }
        for (int j = a[i].F; j <= a[i].S; j++) {
            T.update(j, dp[i][j]);
        }
    }
    int S = 0;
    for (int i = 0; i < n; i++) {
        for (int j = a[i].F; j <= a[i].S; j++) {
            S = mod(S + dp[i][j]);
        }
    }
    cout << S << "\n";
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Incorrect 3 ms 512 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Incorrect 3 ms 512 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2102 ms 277588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 3 ms 640 KB Output is correct
16 Incorrect 3 ms 512 KB Output isn't correct
17 Halted 0 ms 0 KB -