結果
| 問題 | No.1649 Manhattan Square |
| ユーザー |
 ei1333333
|
| 提出日時 | 2021-08-13 21:42:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 253 ms / 3,000 ms |
| コード長 | 6,889 bytes |
| コンパイル時間 | 3,004 ms |
| コンパイル使用メモリ | 217,264 KB |
| 最終ジャッジ日時 | 2025-01-23 18:34:21 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 43 |
ソースコード
#include<bits/stdc++.h>using namespace std;using int64 = long long;// const int mod = 1e9 + 7;const int mod = 998244353;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}template< int mod >struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int) (1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(int64_t n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt< mod >(t);return (is);}static int get_mod() { return mod; }};using modint = ModInt< mod >;/*** @brief Binary-Indexed-Tree(BIT)* @docs docs/binary-indexed-tree.md*/template< typename T >struct BinaryIndexedTree {private:vector< T > data;public:BinaryIndexedTree() = default;explicit BinaryIndexedTree(size_t sz) : data(sz + 1, 0) {}explicit BinaryIndexedTree(const vector< T > &vs) : data(vs.size() + 1, 0) {for(size_t i = 0; i < vs.size(); i++) data[i + 1] = vs[i];for(size_t i = 1; i < data.size(); i++) {size_t j = i + (i & -i);if(j < data.size()) data[j] += data[i];}}void add(int k, const T &x) {for(++k; k < (int) data.size(); k += k & -k) data[k] += x;}T fold(int r) const {T ret = T();for(; r > 0; r -= r & -r) ret += data[r];return ret;}T fold(int l, int r) const {return fold(r) - fold(l);}int lower_bound(T x) const {int i = 0;for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) {if(i + k < data.size() && data[i + k] < x) {x -= data[i + k];i += k;}}return i;}int upper_bound(T x) const {int i = 0;for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) {if(i + k < data.size() && data[i + k] <= x) {x -= data[i + k];i += k;}}return i;}};int main() {int N;cin >> N;vector< pair< int, int > > d(N);cin >> d;sort(begin(d), end(d));vector< int > X(N), Y(N);for(int i = 0; i < N; i++) {tie(X[i], Y[i]) = d[i];}auto calc_diff = [](const vector< int > &f, const vector< int > &g) {vector< int > gs{g};sort(begin(gs), end(gs));gs.erase(unique(begin(gs), end(gs)), end(gs));int M = (int) gs.size();int N = (int) f.size();vector< int > z(N);for(int i = 0; i < N; i++) {z[i] = lower_bound(begin(gs), end(gs), g[i]) - begin(gs);}BinaryIndexedTree< modint > bit1(M), bit2(M), bit3(M), bit4(M);for(int i = 0; i < N; i++) {bit1.add(z[i], modint(f[i]) * g[i]);bit2.add(z[i], 1);bit3.add(z[i], f[i]);bit4.add(z[i], g[i]);}modint ret = 0;for(int i = 0; i < N; i++) {bit1.add(z[i], -modint(f[i]) * g[i]);bit2.add(z[i], -1);bit3.add(z[i], -f[i]);bit4.add(z[i], -g[i]);// g[i]<g[j]{ret += bit1.fold(z[i] + 1, M);ret += bit2.fold(z[i] + 1, M) * f[i] * g[i];ret -= modint(g[i]) * bit3.fold(z[i] + 1, M);ret -= modint(f[i]) * bit4.fold(z[i] + 1, M);}// g[i]>g[j]{ret -= bit1.fold(0, z[i]);ret -= bit2.fold(0, z[i]) * f[i] * g[i];ret += modint(g[i]) * bit3.fold(0, z[i]);ret += modint(f[i]) * bit4.fold(0, z[i]);}}return ret;};auto calc_sq = [](const vector< int > &f) {int N = (int) f.size();modint ret = 0;modint all = 0;for(int i = 0; i < N; i++) {all += f[i];ret += modint(f[i]) * f[i] * (N - 1);}for(int i = 0; i < N; i++) {all -= f[i];ret -= all * f[i] * 2;}return ret;};modint ret = 0;ret += calc_sq(X);ret += calc_sq(Y);ret += calc_diff(X, Y) * 2;cout << ret << "\n";}