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

提出ソース

結果

問題	No.1919 Many Monster Battles
ユーザー	SSRS
提出日時	2022-04-29 23:48:06
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	7,047 bytes
コンパイル時間	2,438 ms
コンパイル使用メモリ	195,120 KB
実行使用メモリ	105,872 KB
最終ジャッジ日時	2024-06-29 05:36:19
合計ジャッジ時間	6,975 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,624 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	11 ms 5,376 KB
testcase_04	AC	11 ms 5,376 KB
testcase_05	AC	12 ms 5,376 KB
testcase_06	AC	11 ms 5,376 KB
testcase_07	AC	12 ms 5,376 KB
testcase_08	AC	12 ms 5,376 KB
testcase_09	AC	12 ms 5,376 KB
testcase_10	AC	11 ms 5,376 KB
testcase_11	AC	11 ms 5,376 KB
testcase_12	AC	11 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
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<int> 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<int> ans(qcnt, 0);
    FenwickTree1D<int> 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);
  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<int> ans1 = solve(q1);
  vector<int> ans2 = solve(q2);
  for (int j = 0; j < N; j++){
    int p = id[j];
    ans[0] += (long long) a[p] * ans1[j] % MOD;
    ans[0] += MOD - (long long) a[p] * ans2[j] % MOD;
    ans[0] += (long long) a[p] * ans2[N * 2 - 1 - j] % MOD;
    ans[0] += MOD - (long long) a[p] * ans1[N * 2 - 1 - j] % MOD;
    ans[1] += MOD - (long long) b[p] * ans1[j] % MOD;
    ans[1] += MOD - (long long) b[p] * ans2[j] % MOD;
    ans[1] += (long long) b[p] * ans2[N * 2 - 1 - j] % MOD;
    ans[1] += (long long) b[p] * ans1[N * 2 - 1 - j] % MOD;
  }
  for (int i = 0; i < 2; i++){
    ans[i] %= MOD;
    ans[i] += MOD;
    ans[i] *= 2;
    ans[i] %= MOD;
  }
  vector<int> b2 = b;
  sort(b2.begin(), b2.end());
  for (int i = 0; i < N; i++){
    ans[1] += (long long) b2[i] * (i * 2 - N + 1 + MOD)* 2 % MOD;
  }
  ans[1] %= MOD;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
      if (abs(a[i] - a[j]) == abs(b[i] - b[j])){
        ans[1] -= abs(b[i] - b[j]);
        if (ans[1] < 0){
          ans[1] += MOD;
        }
      }
    }
  }
  cout << ans[0] << ' ' << ans[1] << endl;
}

yukicoder

結果

テストケース

ソースコード