oj.uz

Submission #480659

# Submission time Handle Problem Language Result Execution time Memory
480659 2021-10-17T14:54:12 Z TAMREF Boat (APIO16_boat) C++17
36 / 100
 2000 ms 4316 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct mint {
    static const int mod = 1e9 + 7;
    int v;
    mint(ll v = 0) : v(v % mod) {}
    mint operator+ (mint o) {
        return mint(v + o.v);
    }
    mint operator- (mint o) {
        return mint(v + mod - o.v);
    }
    mint operator* (mint o) {
        return mint(ll(v) * o.v);
    }
    mint operator^ (int n) {
        mint ret(1), pv(v);
        for(;n;n>>=1) {
            if(n & 1) ret = ret * pv;
            pv = pv * pv;
        }
        return ret;
    }
    mint inv() {
        return mint(v) ^ (mod - 2);
    }
    mint operator/ (mint o) {
        return mint(v) * o.inv();
    }
};

mint& operator+= (mint &a, mint b) {
    return a = a + b;
}

mint& operator-= (mint &a, mint b) {
    return a = a - b;
}

int n;
vector<int> cmp;
int a[505], b[505];

mint a_Ijk[2][1005][505]; // i' < i, j' = j, k' = k
mint b_ij[2][1005]; //i' < i, j' < j, k' arb
mint ans;

int main(){
    fio;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ++b[i];
        cmp.pp(a[i]); cmp.pp(b[i]);
    }
    sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());
    int d = szz(cmp);
    for(int i = 1; i <= n; i++) {
        a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1;
        b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < d; j++) {
            b_ij[i & 1][j] = b_ij[~i & 1][j] + b_ij[i & 1][j-1] - b_ij[~i & 1][j-1];
            for(int k = 1; k <= n; k++) {
                a_Ijk[i & 1][j][k] = a_Ijk[~i & 1][j][k];
                mint dp;
                if(a[i] <= j && j < b[i]) {
                    mint len = cmp[j] - cmp[j-1];
                    if(k == 1) {
                        dp = (mint(1) + b_ij[~i & 1][j-1]) * len;
                    }else{
                        dp = a_Ijk[~i & 1][j][k-1] * (len - mint(k - 1)) / mint(k);
                    }
                }
                a_Ijk[i & 1][j][k] += dp;
                b_ij[i & 1][j] += dp;
                ans += dp;
            }
        }
    }
    cout << (ans).v << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1642 ms 4300 KB Output is correct
2 Correct 1670 ms 4312 KB Output is correct
3 Correct 1630 ms 4300 KB Output is correct
4 Correct 1627 ms 4300 KB Output is correct
5 Correct 1631 ms 4300 KB Output is correct
6 Correct 1631 ms 4304 KB Output is correct
7 Correct 1632 ms 4300 KB Output is correct
8 Correct 1646 ms 4300 KB Output is correct
9 Correct 1644 ms 4300 KB Output is correct
10 Correct 1626 ms 4300 KB Output is correct
11 Correct 1607 ms 4300 KB Output is correct
12 Correct 1673 ms 4300 KB Output is correct
13 Correct 1792 ms 4300 KB Output is correct
14 Correct 1621 ms 4304 KB Output is correct
15 Correct 1645 ms 4304 KB Output is correct
16 Correct 325 ms 4304 KB Output is correct
17 Correct 339 ms 4304 KB Output is correct
18 Correct 328 ms 4300 KB Output is correct
19 Correct 363 ms 4300 KB Output is correct
20 Correct 335 ms 4300 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1642 ms 4300 KB Output is correct
2 Correct 1670 ms 4312 KB Output is correct
3 Correct 1630 ms 4300 KB Output is correct
4 Correct 1627 ms 4300 KB Output is correct
5 Correct 1631 ms 4300 KB Output is correct
6 Correct 1631 ms 4304 KB Output is correct
7 Correct 1632 ms 4300 KB Output is correct
8 Correct 1646 ms 4300 KB Output is correct
9 Correct 1644 ms 4300 KB Output is correct
10 Correct 1626 ms 4300 KB Output is correct
11 Correct 1607 ms 4300 KB Output is correct
12 Correct 1673 ms 4300 KB Output is correct
13 Correct 1792 ms 4300 KB Output is correct
14 Correct 1621 ms 4304 KB Output is correct
15 Correct 1645 ms 4304 KB Output is correct
16 Correct 325 ms 4304 KB Output is correct
17 Correct 339 ms 4304 KB Output is correct
18 Correct 328 ms 4300 KB Output is correct
19 Correct 363 ms 4300 KB Output is correct
20 Correct 335 ms 4300 KB Output is correct
21 Execution timed out 2078 ms 4300 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 4300 KB Output is correct
2 Correct 114 ms 4316 KB Output is correct
3 Correct 127 ms 4300 KB Output is correct
4 Correct 130 ms 4300 KB Output is correct
5 Correct 137 ms 4300 KB Output is correct
6 Correct 186 ms 4280 KB Output is correct
7 Correct 185 ms 4300 KB Output is correct
8 Correct 190 ms 4280 KB Output is correct
9 Correct 182 ms 4300 KB Output is correct
10 Correct 185 ms 4300 KB Output is correct
11 Correct 137 ms 4280 KB Output is correct
12 Correct 114 ms 4300 KB Output is correct
13 Correct 130 ms 4172 KB Output is correct
14 Correct 126 ms 4300 KB Output is correct
15 Correct 135 ms 4296 KB Output is correct
16 Correct 82 ms 4300 KB Output is correct
17 Correct 75 ms 4300 KB Output is correct
18 Correct 79 ms 4280 KB Output is correct
19 Correct 73 ms 4300 KB Output is correct
20 Correct 81 ms 4300 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1642 ms 4300 KB Output is correct
2 Correct 1670 ms 4312 KB Output is correct
3 Correct 1630 ms 4300 KB Output is correct
4 Correct 1627 ms 4300 KB Output is correct
5 Correct 1631 ms 4300 KB Output is correct
6 Correct 1631 ms 4304 KB Output is correct
7 Correct 1632 ms 4300 KB Output is correct
8 Correct 1646 ms 4300 KB Output is correct
9 Correct 1644 ms 4300 KB Output is correct
10 Correct 1626 ms 4300 KB Output is correct
11 Correct 1607 ms 4300 KB Output is correct
12 Correct 1673 ms 4300 KB Output is correct
13 Correct 1792 ms 4300 KB Output is correct
14 Correct 1621 ms 4304 KB Output is correct
15 Correct 1645 ms 4304 KB Output is correct
16 Correct 325 ms 4304 KB Output is correct
17 Correct 339 ms 4304 KB Output is correct
18 Correct 328 ms 4300 KB Output is correct
19 Correct 363 ms 4300 KB Output is correct
20 Correct 335 ms 4300 KB Output is correct
21 Execution timed out 2078 ms 4300 KB Time limit exceeded
22 Halted 0 ms 0 KB -