제출 #653755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653755		ksjsjsjsjsjsjs	Boat (APIO16_boat)	C++14	100 / 100	1295 ms	6352 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
	GOAT
----------------------------------------------------------------
*/
const int M = 1e9 + 7;
const int N = 502;
const int Nx2 = 1002;
int n, m, inv[N], d[Nx2][N][2], d1[Nx2][N];
pi a[N];
vpi seg;
stack<pi> s;
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n;
    FOR(i, 1, n) cin >> a[i].st >> a[i].nd;
    seg.pb({1, 1e9});
    FOR(i, 1, n) {
        EACH(j, seg) {
            int l = j.st, r = j.nd;
            if (a[i].st > l && a[i].st <= r && a[i].nd >= r) {
            	j = {l, a[i].st - 1};
            	s.push({a[i].st, r});
            }
            else if (a[i].nd < r && a[i].nd >= l && a[i].st <= l) {
            	j = {l, a[i].nd};
            	s.push({a[i].nd + 1, r});
            }
            else if (l < a[i].st && a[i].nd < r) {
            	j = {l, a[i].st - 1};
            	s.push(a[i]);
            	s.push({a[i].nd + 1, r});
            }
        }
        WHILE(!s.empty()) {
        	seg.pb(s.top());
        	s.pop();
        }
    }
    seg.pb({-1, -1});
    sort(all(seg));
    m = sz(seg) - 1;
    inv[1] = 1;
    FOR(i, 2, n) inv[i] = 1LL * (-M / i + M) % M * inv[M % i] % M;
    FOR(i, 1, m) {
        d1[i][0] = 1;
        int cnt = min(n, seg[i].nd - seg[i].st + 1);
        FOR(j, 1, cnt) d1[i][j] = 1LL * d1[i][j - 1] * (seg[i].nd - seg[i].st + 2 - j) % M * inv[j] % M;
    }
    FOR(i, 1, m)
    FOR(j, 0, n)
    FOR(z, 0, 1)
        d[i][j][z] = d1[i][j];
    FOR(i, 1, n)
    FOR(j, 1, m)
    FOR(z, 0, n - i)
    FOR(stat, 0, 1) {
        if (!stat) d[j][z][stat] = 0;
        if (a[i].st <= seg[j].st && seg[j].nd <= a[i].nd) d[j][z][stat] = (d[j][z][stat] + d[j][z + 1][1]) % M;
        if (j > 1) d[j][z][stat] = (d[j][z][stat] + 1LL * d1[j][z] * d[j - 1][0][0] % M) % M;
    }
    cout << (d[m][0][1] - 1 + M) % M;
    return 0;
}
/*
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

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

boat.cpp: In function 'int main()':
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:61:5: note: in expansion of macro 'FOR'
   61 |     FOR(i, 1, n) cin >> a[i].st >> a[i].nd;
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:63:5: note: in expansion of macro 'FOR'
   63 |     FOR(i, 1, n) {
      |     ^~~
boat.cpp:34:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   34 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
boat.cpp:64:9: note: in expansion of macro 'EACH'
   64 |         EACH(j, seg) {
      |         ^~~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:89:5: note: in expansion of macro 'FOR'
   89 |     FOR(i, 2, n) inv[i] = 1LL * (-M / i + M) % M * inv[M % i] % M;
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:90:5: note: in expansion of macro 'FOR'
   90 |     FOR(i, 1, m) {
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:93:9: note: in expansion of macro 'FOR'
   93 |         FOR(j, 1, cnt) d1[i][j] = 1LL * d1[i][j - 1] * (seg[i].nd - seg[i].st + 2 - j) % M * inv[j] % M;
      |         ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:95:5: note: in expansion of macro 'FOR'
   95 |     FOR(i, 1, m)
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:96:5: note: in expansion of macro 'FOR'
   96 |     FOR(j, 0, n)
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:97:5: note: in expansion of macro 'FOR'
   97 |     FOR(z, 0, 1)
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:99:5: note: in expansion of macro 'FOR'
   99 |     FOR(i, 1, n)
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:100:5: note: in expansion of macro 'FOR'
  100 |     FOR(j, 1, m)
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:101:5: note: in expansion of macro 'FOR'
  101 |     FOR(z, 0, n - i)
      |     ^~~
boat.cpp:30:31: warning: unnecessary parentheses in declaration of 'stat' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
boat.cpp:102:5: note: in expansion of macro 'FOR'
  102 |     FOR(stat, 0, 1) {
      |     ^~~

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