oj.uz

Submission #242163

# Submission time Handle Problem Language Result Execution time Memory
242163 2020-06-27T03:54:12 Z WhaleVomit Boat (APIO16_boat) C++14
9 / 100
 1402 ms 13944 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

const ll MOD = 1000000007;
const int MAX_N = 505;
int n;
pi arr[MAX_N];
ll fact[MAX_N];
ll factor[MAX_N*4][MAX_N];
vector<ll> dp[4*MAX_N];

bool cont(pi p1, pi p2) {
    return p2.f <= p1.f && p1.s <= p2.s;
}

int len(pi p) {
    return p.s - p.f + 1;
}

ll mpow(ll base, ll exp) {
    if(exp == 0) return 1;
    ll res = mpow(base, exp/2);
    res *= res; res %= MOD;
    if(exp%2 == 1) {
        res *= base; res %= MOD;
    }
    return res;
}

ll inv(ll k) {
    return mpow(k, MOD-2);
}

ll getSum(int j, vector<ll>& v) {
    ll res = 0;
    int tot = sz(v);
    M00(idx, tot) {
        ll val = (v[idx] * factor[j][tot-idx-1]) % MOD;
        res += val;
        res %= MOD;
    }
    return res;
}

int main() { FAST
    fact[0] = 1;
    MOO(i, 1, MAX_N) fact[i] = (fact[i-1] * i) % MOD;
    cin >> n;
    M00(i, n) cin >> arr[i].f >> arr[i].s;
    vi idxs;
    idxs.pb(0);
    M00(i, n) {
        idxs.pb(arr[i].f);
        idxs.pb(arr[i].s);
    }
    sort(all(idxs));
    idxs.erase(unique(all(idxs)), idxs.end());
    vector<pi> intervals;
    intervals.pb(mp(0,0));
    MOO(i, 1, sz(idxs)) {
        pi p = mp(idxs[i-1]+1, idxs[i]-1);
        if(p.f <= p.s) intervals.pb(p);
        intervals.pb(mp(idxs[i], idxs[i]));
    }
    sort(all(intervals));
    M00(i, sz(intervals)) {
        ll x = len(intervals[i]);
        ll cur = 1;
        M00(j, MAX_N-1) {
            cur *= x+j; cur %= MOD;
            factor[i][j] = (cur * inv(fact[j+1])) % MOD;
        }
    }

    dp[0].pb(1);
    MOO(i, 1, sz(intervals)) {
        if(cont(intervals[i], arr[0])) dp[i].pb(1);
        else dp[i].pb(0);
    }
    MOO(i, 1, n) {
        ll cursum = 0;
        M00(j, sz(intervals)) {
            ll add = getSum(j, dp[j]);
            if(cont(intervals[j], arr[i])) {
                dp[j].pb(cursum);
            } else {
                dp[j].pb(0);
            }
            cursum += add;
            cursum %= MOD;
        }
    }
    ll ans = MOD-1;
    M00(i, sz(intervals)) {
        ans += getSum(i, dp[i]);
        ans %= MOD;
    }
    finish(ans);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 8568 KB Output is correct
2 Correct 794 ms 8568 KB Output is correct
3 Correct 794 ms 8568 KB Output is correct
4 Correct 795 ms 8620 KB Output is correct
5 Correct 798 ms 8568 KB Output is correct
6 Correct 797 ms 8440 KB Output is correct
7 Correct 807 ms 8444 KB Output is correct
8 Correct 808 ms 8568 KB Output is correct
9 Correct 807 ms 8568 KB Output is correct
10 Correct 798 ms 8476 KB Output is correct
11 Correct 802 ms 8464 KB Output is correct
12 Correct 801 ms 8568 KB Output is correct
13 Correct 801 ms 8568 KB Output is correct
14 Correct 808 ms 8568 KB Output is correct
15 Correct 810 ms 8440 KB Output is correct
16 Correct 135 ms 1784 KB Output is correct
17 Correct 149 ms 2040 KB Output is correct
18 Correct 139 ms 1912 KB Output is correct
19 Correct 148 ms 2040 KB Output is correct
20 Correct 143 ms 1912 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 8568 KB Output is correct
2 Correct 794 ms 8568 KB Output is correct
3 Correct 794 ms 8568 KB Output is correct
4 Correct 795 ms 8620 KB Output is correct
5 Correct 798 ms 8568 KB Output is correct
6 Correct 797 ms 8440 KB Output is correct
7 Correct 807 ms 8444 KB Output is correct
8 Correct 808 ms 8568 KB Output is correct
9 Correct 807 ms 8568 KB Output is correct
10 Correct 798 ms 8476 KB Output is correct
11 Correct 802 ms 8464 KB Output is correct
12 Correct 801 ms 8568 KB Output is correct
13 Correct 801 ms 8568 KB Output is correct
14 Correct 808 ms 8568 KB Output is correct
15 Correct 810 ms 8440 KB Output is correct
16 Correct 135 ms 1784 KB Output is correct
17 Correct 149 ms 2040 KB Output is correct
18 Correct 139 ms 1912 KB Output is correct
19 Correct 148 ms 2040 KB Output is correct
20 Correct 143 ms 1912 KB Output is correct
21 Incorrect 1402 ms 13944 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 8568 KB Output is correct
2 Correct 794 ms 8568 KB Output is correct
3 Correct 794 ms 8568 KB Output is correct
4 Correct 795 ms 8620 KB Output is correct
5 Correct 798 ms 8568 KB Output is correct
6 Correct 797 ms 8440 KB Output is correct
7 Correct 807 ms 8444 KB Output is correct
8 Correct 808 ms 8568 KB Output is correct
9 Correct 807 ms 8568 KB Output is correct
10 Correct 798 ms 8476 KB Output is correct
11 Correct 802 ms 8464 KB Output is correct
12 Correct 801 ms 8568 KB Output is correct
13 Correct 801 ms 8568 KB Output is correct
14 Correct 808 ms 8568 KB Output is correct
15 Correct 810 ms 8440 KB Output is correct
16 Correct 135 ms 1784 KB Output is correct
17 Correct 149 ms 2040 KB Output is correct
18 Correct 139 ms 1912 KB Output is correct
19 Correct 148 ms 2040 KB Output is correct
20 Correct 143 ms 1912 KB Output is correct
21 Incorrect 1402 ms 13944 KB Output isn't correct
22 Halted 0 ms 0 KB -