結果

問題 No.122 傾向と対策：門松列（その３）
コンテスト
ユーザー assy1028
提出日時 2016-12-23 15:37:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 5,845 bytes
コンパイル時間 1,278 ms
コンパイル使用メモリ 104,292 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-14 16:53:44
合計ジャッジ時間 1,576 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0