제출 #44897

#제출 시각아이디문제언어결과실행 시간메모리
44897KerimBoat (APIO16_boat)C++17
100 / 100
1286 ms2676 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)
#define endl '\n'
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define mp make_pair
#define nd second
#define st first
#define type(x) __typeof(x.begin())
 
typedef pair < int ,int > pii;
 
typedef long long ll;
 
const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9 + 7;
const int N = 2e5 + 5;
 
int F[N], P[N], con[N], m, pre[N], n, l, r, x, y, z, dp[N], dd[505][505];
map< int , vector< int > > add, del;
map< int , int > H;
vector< int > v;
 
int FE(int x, int k) {
    if(!k) return 1;
    int temp = FE(x, k / 2);
    if(k & 1) return (ll) temp * temp % mod * x % mod;
    return (ll) temp * temp % mod;
}
 
int GO(int x, int y) {
    int ans = 1;
    FOR(i, 1, y) ans = ans * (ll) x-- % mod;
    return ans;
}
 
void calc(int x) {
    FOR(i, 1, m) {
        con[i] = GO(x, i) * (ll) F[i] % mod;
    }
}
 
int NX(type(H) it) {
    it++;
    if(it == H.end()) return inf + 5;
    return it->st;
}
 
int f(int x, int y) {
    if(y == 0 || x == 0 || y > x) return 0;
    int &r = dd[x][y];
    if(r != -1) return r;
    if(y == 1) return r = (pre[v[x] - 1] + f(x - 1, y)) % mod;
    return r = (f(x - 1, y) + f(x - 1, y - 1)) % mod;
}
 
int main() {
	//~ freopen("file.in","r",stdin);
    scanf("%d", &n);
 
    P[0] = 1;
    FOR(i, 1, n) P[i] = P[i-1] * (ll) i % mod;
    FOR(i, 0, n) F[i] = FE(P[i], mod - 2);
 
    FOR(i, 1, n) {
        scanf("%d %d", &l, &r);
        add[l].pb(i);
        del[r + 1].pb(i);
        H[l] = H[r + 1] = 1;
    }
 
    set< int > S;
 
    foreach(tt, H) {
        int p = tt->st, next = NX(tt);
        foreach(it, add[p]) S.insert(*it);
        foreach(it, del[p]) S.erase(S.find(*it));
        if(S.size()) {
            v.clear();
            pre[0] = 1; FOR(i, 1, n) pre[i] = (dp[i] + pre[i-1]) % mod;
            v.pb(0); foreach(it, S) v.pb(*it);
            m = v.size() - 1;
            calc(next - p);
            memset(dd, -1, sizeof dd);
            FOR(i, 1, m)
                FOR(j, 1, i) {
                    if(j == 1) {
                        dp[v[i]] = (dp[v[i]] + con[j] * (ll) pre[v[i] - 1]) % mod;
                    }
                    else {
                        dp[v[i]] = (dp[v[i]] + con[j] * (ll) f(i - 1, j - 1)) % mod;
                    }
                }
        }
    }
 
    dp[0] = 0;
    FOR(i, 1, n) dp[i] = (dp[i] + dp[i-1]) % mod;
 
    cout << dp[n] << endl;
 
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...