제출 #653754

#제출 시각아이디문제언어결과실행 시간메모리
653754ksjsjsjsjsjsjsBoat (APIO16_boat)C++14
100 / 100
1246 ms6348 KiB
#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, seg1; 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) { seg1.clear(); 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}; seg1.pb({a[i].st, r}); } else if (a[i].nd < r && a[i].nd >= l && a[i].st <= l) { j = {l, a[i].nd}; seg1.pb({a[i].nd + 1, r}); } else if (l < a[i].st && a[i].nd < r) { j = {l, a[i].st - 1}; seg1.pb(a[i]); seg1.pb({a[i].nd + 1, r}); } } EACH(j, seg1) seg.pb(j); } 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:60:5: note: in expansion of macro 'FOR'
   60 |     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:62:5: note: in expansion of macro 'FOR'
   62 |     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:34:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   34 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
boat.cpp:80:9: note: in expansion of macro 'EACH'
   80 |         EACH(j, seg1) seg.pb(j);
      |         ^~~~
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:86:5: note: in expansion of macro 'FOR'
   86 |     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:87:5: note: in expansion of macro 'FOR'
   87 |     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:90:9: note: in expansion of macro 'FOR'
   90 |         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:92:5: note: in expansion of macro 'FOR'
   92 |     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:5: note: in expansion of macro 'FOR'
   93 |     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:94:5: note: in expansion of macro 'FOR'
   94 |     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:96:5: note: in expansion of macro 'FOR'
   96 |     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:97:5: note: in expansion of macro 'FOR'
   97 |     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:98:5: note: in expansion of macro 'FOR'
   98 |     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:99:5: note: in expansion of macro 'FOR'
   99 |     FOR(stat, 0, 1) {
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...