#757233 (C++14) No.1919 Many Monster Battles

提出ソース

結果

問題	No.1919 Many Monster Battles
ユーザー	SSRS
提出日時	2022-04-29 23:30:01
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,561 bytes
コンパイル時間	2,702 ms
コンパイル使用メモリ	195,204 KB
実行使用メモリ	110,028 KB
最終ジャッジ日時	2024-06-29 05:15:59
合計ジャッジ時間	6,900 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,752 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	15 ms 5,376 KB
testcase_04	AC	14 ms 5,376 KB
testcase_05	AC	14 ms 5,376 KB
testcase_06	AC	15 ms 5,376 KB
testcase_07	AC	15 ms 5,376 KB
testcase_08	AC	14 ms 5,376 KB
testcase_09	AC	14 ms 5,376 KB
testcase_10	AC	14 ms 5,376 KB
testcase_11	AC	14 ms 5,376 KB
testcase_12	AC	15 ms 5,376 KB
testcase_13	TLE	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000001;
const long long MOD = 1000000007;
//https://judge.yosupo.jp/submission/81486
typedef long long ll;
template <class T, class Op = plus<T>>
struct FenwickTree1D
{
    int N;
    vector<T> BIT;
    Op op;
    FenwickTree1D(int N, T qdef = T(), Op op = Op())
        : N(N), BIT(N + 1, qdef), op(op) {}
    template <class F>
    FenwickTree1D(int N, F f, T qdef = T(), Op op = Op())
        : FenwickTree1D(N, qdef, op)
    {
        for (int i = 1; i <= N; i++)
        {
            BIT[i] = op(BIT[i], f());
            int j = i + (i & -i);
            if (j <= N)
                BIT[j] = op(BIT[j], BIT[i]);
        }
    }
    template <class It>
    FenwickTree1D(It st, It en, T qdef = T(), Op op = Op())
        : FenwickTree1D(
              en - st, [&]
              { return *st++; },
              qdef, op)
    {
    }
    template <class Inv = minus<T>>
    vector<T> values(Inv inv = Inv())
    {
        vector<T> ret(BIT.begin() + 1, BIT.end());
        for (int i = N; i >= 1; i--)
        {
            int j = i + (i & -i);
            if (j <= N)
                ret[j - 1] = inv(ret[j - 1], ret[i - 1]);
        }
        return ret;
    }
    void update(int i, T v)
    {
        for (i++; i <= N; i += i & -i)
            BIT[i] = op(BIT[i], v);
    }
    T query(int r)
    {
        T ret = BIT[0];
        for (r++; r > 0; r -= r & -r)
            ret = op(ret, BIT[r]);
        return ret;
    }
    template <class Inv = minus<T>>
    T query(int l, int r, Inv inv = Inv())
    {
        return inv(query(r), query(l - 1));
    }
    template <class F>
    int bsearch(T v, F cmp)
    {
        T agg = BIT[0];
        int ind = 0;
        for (int j = __lg(N + 1); j >= 0; j--)
        {
            int i = ind + (1 << j);
            if (i <= N && cmp(op(agg, BIT[i]), v))
                agg = op(agg, BIT[ind = i]);
        }
        return ind;
    }
};
// add (x, y, v)
// query [x1, x2] x [y1, y2]
struct Query
{
    int t, xlo, xhi, ylo, yhi, v;
    Query(int t, int xlo, int xhi, int ylo, int yhi, int v) : t(t), xlo(xlo), xhi(xhi), ylo(ylo), yhi(yhi), v(v) {}
};

void add_point(vector<Query>& queries, int x, int y, int v) { queries.push_back(Query(0, x, x, y, y, v)); }

void add_query(vector<Query>& queries, int l, int r, int d, int u) { queries.push_back(Query(1, l, r - 1, d, u - 1, 0)); }

struct Event
{
    int t, x, ylo, yhi, v;
    Event(int t, int x, int ylo, int yhi, int v) : t(t), x(x), ylo(ylo), yhi(yhi), v(v) {}
    bool operator<(const Event &e) const { return make_pair(x, t) < make_pair(e.x, e.t); }
};

vector<ll> solve(vector<Query> queries)
{
    vector<Event> events;
    events.reserve(queries.size() * 2);
    vector<int> YS;
    YS.reserve(queries.size());
    for (auto &&q : queries)
        if (q.t == 0)
            YS.push_back(q.ylo);
    sort(YS.begin(), YS.end());
    YS.erase(unique(YS.begin(), YS.end()), YS.end());
    int qcnt = 0;
    for (auto &&q : queries)
    {
        if (q.t == 0)
            q.ylo = lower_bound(YS.begin(), YS.end(), q.ylo) - YS.begin();
        else
        {
            q.ylo = lower_bound(YS.begin(), YS.end(), q.ylo) - YS.begin();
            q.yhi = int(upper_bound(YS.begin(), YS.end(), q.yhi) - YS.begin()) - 1;
            q.v = qcnt++;
            if (q.ylo > q.yhi)
                q.t = -1;
        }
    }
    vector<ll> ans(qcnt, 0);
    FenwickTree1D<ll> FT(YS.size());
    function<void(int, int)> rec = [&](int l, int r)
    {
        if (l == r)
            return;
        int m = l + (r - l) / 2;
        rec(l, m);
        rec(m + 1, r);
        events.clear();
        for (int i = l; i <= m; i++)
            if (queries[i].t == 0)
                events.emplace_back(0, queries[i].xlo, queries[i].ylo, queries[i].ylo, queries[i].v);
        if (events.empty())
            return;
        int curSize = events.size();
        for (int i = m + 1; i <= r; i++)
            if (queries[i].t == 1)
            {
                events.emplace_back(-1, queries[i].xlo, queries[i].ylo, queries[i].yhi, queries[i].v);
                events.emplace_back(1, queries[i].xhi, queries[i].ylo, queries[i].yhi, queries[i].v);
            }
        if (curSize == int(events.size()))
            return;
        sort(events.begin(), events.end());
        for (auto &&e : events)
        {
            if (e.t == 0)
                FT.update(e.ylo, e.v);
            else
                ans[e.v] += e.t * FT.query(e.ylo, e.yhi);
        }
        for (auto &&e : events)
            if (e.t == 0)
                FT.update(e.ylo, -e.v);
    };
    if (qcnt > 0)
        rec(0, int(queries.size()) - 1);
    return ans;
}

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  vector<int> b(N);
  for (int i = 0; i < N; i++){
    cin >> b[i];
  }
  vector<long long> ans(2, 0);
  for (int i = 0; i < 2; i++){
    vector<pair<int, int>> P(N);
    for (int j = 0; j < N; j++){
      P[j] = make_pair(a[j], b[j]);
    }
    sort(P.begin(), P.end());
    for (int j = 0; j < N; j++){
      a[j] = P[j].first;
      b[j] = P[j].second;
    }
    vector<pair<int, int>> P2(N);
    for (int j = 0; j < N; j++){
      P2[j] = make_pair(b[j], j);
    }
    sort(P2.begin(), P2.end());
    vector<int> id(N);
    for (int j = 0; j < N; j++){
      id[j] = P2[j].second;
    }
    vector<Query> q1, q2;
    for (int j = 0; j < N; j++){
      int p = id[j];
      add_query(q1, 0, p, -INF, a[p] - b[p]);
      add_query(q2, p + 1, N, a[p] + b[p] + 1, INF);
      add_point(q1, p, a[p] - b[p], 1);
      add_point(q2, p, a[p] + b[p], 1);
    }
    for (int j = 0; j < N; j++){
      add_point(q1, j, a[j] - b[j], -1);
      add_point(q2, j, a[j] + b[j], -1);
    }
    for (int j = N - 1; j >= 0; j--){
      int p = id[j];
      add_query(q2, 0, p, -INF, a[p] + b[p]);
      add_query(q1, p + 1, N, a[p] - b[p] + 1, INF);
      add_point(q1, p, a[p] - b[p], 1);
      add_point(q2, p, a[p] + b[p], 1);
    }
    vector<long long> ans1 = solve(q1);
    vector<long long> ans2 = solve(q2);
    for (int j = 0; j < N; j++){
      int p = id[j];
      ans[i] += (long long) a[p] * ans1[j] % MOD;
      ans[i] += MOD - (long long) a[p] * ans2[j] % MOD;
      ans[i] += (long long) a[p] * ans2[N * 2 - 1 - j] % MOD;
      ans[i] += MOD - (long long) a[p] * ans1[N * 2 - 1 - j] % MOD;
    }
    ans[i] %= MOD;
    ans[i] += MOD;
    ans[i] *= 2;
    ans[i] %= MOD;
    swap(a, b);
  }
  cout << ans[0] << ' ' << ans[1] << endl;
}

yukicoder

結果

テストケース

ソースコード