Submission #44897

#	Time	Username	Problem	Language	Result	Execution time	Memory
44897		Kerim	Boat (APIO16_boat)	C++17	100 / 100	1286 ms	2676 KiB

boat

#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;
}

Compilation message (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);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42