結果
問題 | No.1649 Manhattan Square |
ユーザー | 👑 Nachia |
提出日時 | 2021-08-13 22:27:43 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,855 bytes |
コンパイル時間 | 806 ms |
コンパイル使用メモリ | 76,316 KB |
最終ジャッジ日時 | 2024-04-14 18:43:17 |
合計ジャッジ時間 | 2,717 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:9:13: error: 'uint64_t' does not name a type 9 | using u64 = uint64_t; | ^~~~~~~~ main.cpp:7:1: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'? 6 | #include <atcoder/fenwicktree> +++ |+#include <cstdint> 7 | using namespace std;
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <atcoder/modint> #include <atcoder/fenwicktree> using namespace std; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) const i64 MOD = 998244353; using m32 = atcoder::static_modint<MOD>; int lowerBoundIdx(const vector<int>& A, int v){ return lower_bound(A.begin(),A.end(),v) - A.begin(); } m32 solve(vector<pair<int,int>> P){ int n = P.size(); sort(P.begin(),P.end()); vector<int> Y(n); rep(i,n) Y[i] = P[i].second; sort(Y.begin(),Y.end()); atcoder::fenwick_tree<m32> G0(n); atcoder::fenwick_tree<m32> G1(n); atcoder::fenwick_tree<m32> G2(n); m32 ans = 0; for(auto p : P){ int y = lowerBoundIdx(Y,p.second); m32 w = m32(p.first) + p.second; ans += G2.sum(0,y); ans -= G1.sum(0,y) * w * 2; ans += G0.sum(0,y) * w * w; G0.add(y, 1); G1.add(y, w); G2.add(y, w * w); } return ans; } m32 solve2(vector<pair<int,int>> P){ int n = P.size(); sort(P.begin(),P.end()); int prex = -1; m32 G0 = 0; m32 G1 = 0; m32 G2 = 0; m32 ans = 0; rep(i,n){ auto p = P[i]; m32 w = p.second; if(p.first == prex){ ans += G0 * w * w; ans -= 2 * G1 * w; ans += G2; } else{ G0 = G1 = G2 = 0; } G0 += 1; G1 += w; G2 += w * w; prex = P[i].first; } return ans; } int main() { int N; cin >> N; vector<pair<int,int>> X(N); rep(i,N) cin >> X[i].first >> X[i].second; m32 ans = 0; rep(t,2){ rep(i,N) X[i].first = 1000000000 - X[i].first; ans += solve(X); } ans -= solve2(X); rep(i,N) swap(X[i].first,X[i].second); ans += solve2(X); cout << ans.val() << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;