結果

問題 No.1919 Many Monster Battles
ユーザー SSRSSSRS
提出日時 2022-04-29 23:32:05
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,411 bytes
コンパイル時間 6,242 ms
コンパイル使用メモリ 460,816 KB
実行使用メモリ 106,056 KB
最終ジャッジ日時 2024-06-29 05:17:35
合計ジャッジ時間 9,704 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,760 KB
testcase_01 AC 3 ms
6,816 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 15 ms
6,944 KB
testcase_04 AC 14 ms
6,944 KB
testcase_05 AC 14 ms
6,940 KB
testcase_06 AC 14 ms
6,944 KB
testcase_07 AC 15 ms
6,940 KB
testcase_08 AC 14 ms
6,944 KB
testcase_09 AC 14 ms
6,940 KB
testcase_10 AC 14 ms
6,944 KB
testcase_11 AC 14 ms
6,944 KB
testcase_12 AC 15 ms
6,940 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 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:21:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   21 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
main.cpp:28:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   28 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
main.cpp:30:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
main.cpp:44:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   44 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
main.cpp:58:52: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   58 |     FenwickTree1D(int N, T qdef = T(), Op op = Op())
      |                                                    ^
main.cpp:58:52: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
main.cpp:58:52: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
main.cpp:58:52: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
main.cpp:61:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   61 |     FenwickTree1D(int N, F f, T qdef = T(), Op op = Op())
      |                                                         ^
main.cpp:61:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
main.cpp:61:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
main.cpp:61:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
main.cpp:73:59: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   73 |     FenwickTree1D(It st, It en, T qdef = T(), Op op = Op())
      |

ソースコード

diff # 

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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);
  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<int> ans1 = solve(q1);
    vector<int> 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;
}
0