oj.uz

답안 #1087226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087226 2024-09-12T10:31:53 Z mispertion Boat (APIO16_boat) C++17
9 / 100
 669 ms 2900 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 = 1e3 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 516 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 348 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 3 ms 348 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 348 KB Output is correct
17 Correct 1 ms 404 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 516 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 348 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 3 ms 348 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 348 KB Output is correct
17 Correct 1 ms 404 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 299 ms 2132 KB Output is correct
22 Correct 285 ms 2384 KB Output is correct
23 Correct 246 ms 2128 KB Output is correct
24 Correct 282 ms 2288 KB Output is correct
25 Correct 288 ms 2128 KB Output is correct
26 Correct 647 ms 2812 KB Output is correct
27 Correct 665 ms 2808 KB Output is correct
28 Correct 669 ms 2900 KB Output is correct
29 Correct 647 ms 2640 KB Output is correct
30 Runtime error 2 ms 600 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 3 ms 516 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 348 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 3 ms 348 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 348 KB Output is correct
17 Correct 1 ms 404 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 299 ms 2132 KB Output is correct
22 Correct 285 ms 2384 KB Output is correct
23 Correct 246 ms 2128 KB Output is correct
24 Correct 282 ms 2288 KB Output is correct
25 Correct 288 ms 2128 KB Output is correct
26 Correct 647 ms 2812 KB Output is correct
27 Correct 665 ms 2808 KB Output is correct
28 Correct 669 ms 2900 KB Output is correct
29 Correct 647 ms 2640 KB Output is correct
30 Runtime error 2 ms 600 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -