Submission #108389

#TimeUsernameProblemLanguageResultExecution timeMemory
108389kuroniBoat (APIO16_boat)C++17
100 / 100
224 ms504 KiB
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int N = 510, MOD = 1E9 + 7; int n, l, r; bool vis[N]; long long ans = 0, f[N], g[N], c[N], inv[N]; vector<pair<int, int>> sw; vector<int> ve; void init() { c[0] = 1; vis[0] = true; for (int i = 0; i <= n; i++) f[i] = 1; inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; } long long sum(int l, int r) { return f[r] - (l == 0 ? 0 : f[l - 1]); } long long solve(int u, int len) { long long ret = 0; vis[u] = !vis[u]; ve.clear(); for (int i = 0; i <= n; i++) if (vis[i]) ve.push_back(i); for (int i = 1; i < (int)ve.size(); i++) c[i] = c[i - 1] * (len + i - 1) % MOD * inv[i] % MOD; for (int i = 1; i < (int)ve.size(); i++) for (int j = 0; j < i; j++) (g[ve[i]] += c[i - j] * sum(ve[j], ve[j + 1] - 1)) %= MOD; for (int i = 1; i <= n; i++) { (ret += g[i]) %= MOD; (f[i] += ret) %= MOD; g[i] = 0; } return ret; } int main() { scanf("%d", &n); init(); for (int i = 1; i <= n; i++) { scanf("%d%d", &l, &r); sw.push_back({l, i}); sw.push_back({r + 1, i}); } sort(sw.begin(), sw.end()); for (int i = 0; i < (int)sw.size() - 1; i++) (ans += solve(sw[i].second, sw[i + 1].first - sw[i].first)) %= MOD; printf("%lld\n", (ans + MOD) % MOD); }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:59: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...