結果
| 問題 | No.1919 Many Monster Battles |
| ユーザー |
 SSRS
|
| 提出日時 | 2022-04-29 23:32:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 21 |
コンパイルメッセージ
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())
|
ソースコード
#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/81486template <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);elseans[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;}