結果
問題 | No.122 傾向と対策:門松列(その3) |
ユーザー | assy1028 |
提出日時 | 2016-12-23 15:37:45 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 5,845 bytes |
コンパイル時間 | 1,171 ms |
コンパイル使用メモリ | 103,120 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-05-08 12:51:07 |
合計ジャッジ時間 | 1,645 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
5,248 KB |
testcase_01 | AC | 6 ms
5,376 KB |
testcase_02 | AC | 8 ms
5,376 KB |
testcase_03 | AC | 7 ms
5,376 KB |
testcase_04 | AC | 6 ms
5,376 KB |
testcase_05 | AC | 9 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 5 ms
5,376 KB |
ソースコード
#include <algorithm> #include <iostream> #include <cstdio> #include <map> #include <numeric> #include <cmath> #include <set> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <complex> #include <string.h> #include <unordered_set> #include <unordered_map> #include <bitset> #include <iomanip> #include <sys/time.h> #include <random> using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair<ll, ll> P; typedef complex<double> comp; typedef vector< vector<ld> > matrix; struct pairhash { public: template<typename T, typename U> size_t operator()(const pair<T, U> &x) const { size_t seed = hash<T>()(x.first); return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int inf = 1e9 + 9; const ll mod = 1e9 + 7; const double eps = 1e-8; const double pi = acos(-1); ll a[4][2]; ll b[3][2]; // 1 base template<typename T, int max_n> class BIT { private: T bit[max_n + 1]; int n; public: BIT(int _n = max_n) { n = _n; memset(bit, 0, sizeof(bit)); } // [1, i] T sum(int i) { T s = 0; while (i > 0) { s += bit[i]; s %= mod; i -= i & -i; } return s; } // [a, b] T sum(int a, int b) { return (sum(b) - sum(a-1) + mod) % mod; } void add(int i, T x) { while (i <= n) { bit[i] += x; bit[i] %= mod; i += i & -i; } } int lower_bound(T x) { int lb = 0, ub = n; while (ub - lb > 1) { int mid = (ub + lb) / 2; T v = sum(mid); if (v < x) { lb = mid; } else { ub = mid; } } return ub; } int upper_bound(T x) { int lb = 1, ub = n+1; while (ub - lb > 1) { int mid = (ub + lb) / 2; T v = sum(mid); if (v <= x) { lb = mid; } else { ub = mid; } } return ub; } }; BIT<ll, 20010> ua; BIT<ll, 20010> ub; ll da[20010]; ll db[20010]; ll len(P a, P b) { return max(0LL, min(a.first, b.first) - max(a.second, b.second)); } ll len(P a, P b, P c) { ll s = min(a.first, b.first), t = max(a.second, b.second); if (s > t) return len(make_pair(s, t), c); return 0; } ll calc_d_a(ll k, int i, int x, int y, int z) { if (a[i][0] > k || k > a[i][1]) return 0; P w[4]; ll ret = 1; for (int j = 0; j < 4; j++) { if (j == i) continue; ll t = min(k, a[j][1]+1), b = a[j][0]; if (t - b <= 0) return 0; w[j] = make_pair(t, b); ret *= (t - b); } ret -= len(w[x], w[y]) * (w[z].first - w[z].second); ret -= len(w[z], w[y]) * (w[x].first - w[x].second); ret -= len(w[x], w[z]) * (w[y].first - w[y].second); ret += 2 * len(w[x], w[y], w[z]); return ret % mod; } ll calc_d_a(int k) { /* if (k < 20) cerr << k << " " << (calc_d_a(k, 0, 1, 2, 3) + calc_d_a(k, 1, 0, 2, 3) + calc_d_a(k, 2, 1, 0, 3) + calc_d_a(k, 3, 1, 0, 2)) << endl; */ return (calc_d_a(k, 0, 1, 2, 3) + calc_d_a(k, 1, 0, 2, 3) + calc_d_a(k, 2, 1, 0, 3) + calc_d_a(k, 3, 1, 0, 2)) % mod; } ll calc_d_b(ll k, int u, int v, int w) { if (b[u][0] > k || k > b[u][1]) return 0; ll s = min(k,b[v][1]+1) - b[v][0], t = min(k,b[w][1]+1) - b[w][0]; if (s <= 0 || t <= 0) return 0; return s * t - max(0LL, min(k, min(b[v][1]+1, b[w][1]+1)) - max(b[v][0], b[w][0])); } ll calc_d_b(int k) { return (calc_d_b(k, 0, 1, 2) + calc_d_b(k, 1, 0, 2) + calc_d_b(k, 2, 1, 0)) % mod; } ll calc_u_a(ll k, int i, int x, int y, int z) { if (a[i][0] > k || k > a[i][1]) return 0; P w[4]; ll ret = 1; for (int j = 0; j < 4; j++) { if (j == i) continue; ll t = a[j][1], b = max(k, a[j][0]-1); if (t - b <= 0) return 0; w[j] = make_pair(t, b); ret *= (t - b); } ret -= len(w[x], w[y]) * (w[z].first - w[z].second); ret -= len(w[z], w[y]) * (w[x].first - w[x].second); ret -= len(w[x], w[z]) * (w[y].first - w[y].second); ret += 2 * len(w[x], w[y], w[z]); return ret % mod; } ll calc_u_a(int k) { return (calc_u_a(k, 0, 1, 2, 3) + calc_u_a(k, 1, 0, 2, 3) + calc_u_a(k, 2, 1, 0, 3) + calc_u_a(k, 3, 1, 0, 2)) % mod; } ll calc_u_b(ll k, int u, int v, int w) { if (b[u][0] > k || k > b[u][1]) return 0; ll s = b[v][1] - max(k, b[v][0]-1), t = b[w][1] - max(k, b[w][0]-1); if (s <= 0 || t <= 0) return 0; return s * t - max(0LL, min(b[v][1], b[w][1]) - max(k, max(b[v][0]-1, b[w][0]-1))); } ll calc_u_b(int k) { /* if (k < 20) cerr << k << " " << (calc_u_b(k, 0, 1, 2) + calc_u_b(k, 1, 0, 2) + calc_u_b(k, 2, 1, 0)) << endl; */ return (calc_u_b(k, 0, 1, 2) + calc_u_b(k, 1, 0, 2) + calc_u_b(k, 2, 1, 0)) % mod; } ll solve() { for (int i = 1; i <= 20000; i++) { da[i] = calc_d_a(i); db[i] = calc_d_b(i); } for (int i = 1; i <= 20000; i++) { ua.add(i, calc_u_a(i)); ub.add(i, calc_u_b(i)); } ll res = 0; for (int i = 1; i < 20000; i++) { res += da[i] * ub.sum(i+1, 20000); res += db[i] * ua.sum(i+1, 20000); res %= mod; } return res; } void input() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) cin >> a[i][j]; for (int j = 0; j < 2; j++) cin >> b[i][j]; } cin >> a[3][0] >> a[3][1]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); cout << solve() << endl; }