oj.uz

Submission #1087227

# Submission time Handle Problem Language Result Execution time Memory
1087227 2024-09-12T10:32:18 Z mispertion Boat (APIO16_boat) C++17
9 / 100
 669 ms 2964 KB 
#include <bits/stdc++.h>

using namespace std;    
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 2e3 + 10;
const int M = 1e5 + 10;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = 2e18;
const int P = 505319;
const ld eps = 1e-9;

int mult(int a, int b){
    return a * 1LL * b % mod;
}

int sum(int a, int b){
    a %= mod;
    b %= mod;
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

int binpow(int a, int n){
    if (n == 0)
        return 1;
    if (n % 2 == 1){
        return mult(binpow(a, n - 1), a);
    }
    else{
        auto b = binpow(a, n / 2);
        return mult(b, b);
    }
}

int n, l[N], r[N], sm[N], f[N], fi[N];
vector<int> al[N];

int C(int n, int k){
    return mult(f[n], mult(fi[k], fi[n - k]));
}

void solve(){
    cin >> n;
    vector<int> di = {};
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
        di.pb(l[i]);
        di.pb(r[i] + 1);
    }
    di.pb(0);
    sort(all(di));
    di.resize(unique(all(di)) - di.begin());
    sm[0] = 1;
    al[0].pb(1);
    for(int i = 1; i <= n; i++){
        int cur = 0;
        for(int j = 0; j < sz(di) - 1; j++){
            int lr = di[j], rr = di[j + 1] - 1;
            int len = rr - lr + 1;
            if(lr >= l[i] && rr <= r[i]){
                al[j].pb(cur);
                int nsm = 0;
                for(int k = 0; k < sz(al[j]); k++){
                    nsm =sum(nsm, mult(C(sz(al[j]) - k - 1 + len, sz(al[j]) - k), al[j][k]));
                }
                cur = sum(cur, sm[j]);
                sm[j] = nsm;
            }else{
                cur = sum(cur, sm[j]);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < sz(di) - 1; i++)
        ans = sum(ans, sm[i]);
    cout << sum(ans, -1) << '\n';
}   

signed main(){
    mispertion;
    f[0] = 1;
    for(int i = 1; i < N; i++)
        f[i] = mult(f[i - 1], i);
    for(int i = 0; i < N; i++){
        fi[i] = binpow(f[i], mod - 2);
    }
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 1 ms 372 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 294 ms 2232 KB Output is correct
22 Correct 285 ms 2392 KB Output is correct
23 Correct 245 ms 2132 KB Output is correct
24 Correct 281 ms 2132 KB Output is correct
25 Correct 290 ms 2128 KB Output is correct
26 Correct 651 ms 2796 KB Output is correct
27 Correct 669 ms 2964 KB Output is correct
28 Correct 650 ms 2900 KB Output is correct
29 Correct 647 ms 2796 KB Output is correct
30 Runtime error 2 ms 860 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 1 ms 372 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 294 ms 2232 KB Output is correct
22 Correct 285 ms 2392 KB Output is correct
23 Correct 245 ms 2132 KB Output is correct
24 Correct 281 ms 2132 KB Output is correct
25 Correct 290 ms 2128 KB Output is correct
26 Correct 651 ms 2796 KB Output is correct
27 Correct 669 ms 2964 KB Output is correct
28 Correct 650 ms 2900 KB Output is correct
29 Correct 647 ms 2796 KB Output is correct
30 Runtime error 2 ms 860 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -