Submission #251462

#TimeUsernameProblemLanguageResultExecution timeMemory
251462atoizBoat (APIO16_boat)C++14
100 / 100
692 ms3692 KiB
/*input 2 1 2 2 3 */ #include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define FORA(i, a) for (auto &i : a) #define FORB(i, a, b) for (int i = a; i >= b; --i) const int MOD = 1000000007, MAXN = 507; int add(int x, int y) { return x -= ((x += y) >= MOD ? MOD : 0); } int sub(int x, int y) { return x += ((x -= y) < 0 ? MOD : 0); } int mul(int x, int y) { return (int) ((long long) x * y % MOD); } int getinv(int x, int m) { return (x == 1 ? 1 : m - (int) ((long long) m * getinv(m % x, x) / x)); } int N, A[MAXN], B[MAXN], M; int eval[MAXN * 2][MAXN], inv[MAXN], prefsum[MAXN * 2]; vector<int> vals, dp[MAXN * 2]; void addfunc(vector<int> &a, vector<int> b) { a.resize(max(a.size(), b.size())); FOR(i, 0, int(min(a.size(), b.size())) - 1) a[i] = add(a[i], b[i]); } int evalat(vector<int> &a, int x) { int ans = 0; FOR(i, 0, ((int) a.size()) - 1) ans = add(ans, mul(eval[x][i], a[i])); return ans; } vector<int> sumfunc(vector<int> &a) { if (a.empty()) return a; vector<int> b = a; b.insert(b.begin(), 0); return b; } void addint(vector<int> &a, int x) { if (not a.empty()) a[0] = add(a[0], x); else a.push_back(x); } void subint(vector<int> &a, int x) { if (not a.empty()) a[0] = sub(a[0], x); else a.push_back(x ? MOD - x : x); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; FOR(i, 1, N) { cin >> A[i] >> B[i]; --A[i]; vals.push_back(A[i]); vals.push_back(B[i]); } vals.push_back(-1); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); FOR(i, 1, N) { A[i] = (int) (lower_bound(vals.begin(), vals.end(), A[i]) - vals.begin()); B[i] = (int) (lower_bound(vals.begin(), vals.end(), B[i]) - vals.begin()); } FOR(i, 1, N + 5) inv[i] = getinv(i, MOD); M = (int) vals.size() - 1; FOR(i, 1, M) { eval[i][0] = 1; FOR(j, 1, N + 5) eval[i][j] = mul(eval[i][j - 1], mul((vals[i] + j - 1) % MOD, inv[j])); // FOR(j, 1, N + 5) cout << vals[i] << ' ' << j << ": " << eval[i][j] << endl; } FOR(id, 1, N) { int l = A[id], r = B[id]; // cout << l << ' ' << r << " - " << vals[l] << ' ' << vals[r] << endl; FOR(i, 1, r - 2) { vector<int> sumf = sumfunc(dp[i]); int cur = sub(evalat(sumf, i + 1), evalat(sumf, i)); prefsum[i] = add(prefsum[i - 1], cur); // cout << vals[i] << ' ' << vals[i + 1] << ": " << cur << ' ' << dp[i].size() << endl; } // cout << "S" << endl; FORB(i, r - 1, l) { // cout << vals[i] << ' ' << vals[i + 1] << ": " << dp[i].size(); vector<int> sumf = sumfunc(dp[i]); vector<int> vec = sumf; addint(vec, prefsum[i - 1]); subint(vec, evalat(sumf, i)); addint(vec, 1); dp[i] = move(vec); // cout << " " << dp[i].size() << endl; } } // cout << " - " << endl; FOR(i, 1, M - 1) { vector<int> sumf = sumfunc(dp[i]); int cur = sub(evalat(sumf, i + 1), evalat(sumf, i)); prefsum[i] = add(prefsum[i - 1], cur); // cout << vals[i] << ' ' << vals[i + 1] << ": " << cur << ' ' << dp[i].size() << endl; } cout << prefsum[M - 1] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...