結果
問題 | No.1649 Manhattan Square |
ユーザー |
![]() |
提出日時 | 2021-08-13 22:35:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 521 ms / 3,000 ms |
コード長 | 1,860 bytes |
コンパイル時間 | 5,694 ms |
コンパイル使用メモリ | 263,888 KB |
最終ジャッジ日時 | 2025-01-23 20:16:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:47:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 47 | scanf("%d %d",&x[i],&y[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 mint ans = 0; int N; void go(vector<int> x){ sort(x.begin(),x.end()); rep(i,N){ mint t = x[i]; t *= x[i]; t *= N-1; ans += t; } mint sum = 0; rep(i,N){ ans += sum * x[i]; sum -= x[i] * 2; } } mint op(mint a,mint b){ return a+b; } mint e(){ return 0; } int main(){ cin>>N; vector<int> x(N),y(N); vector<int> t; rep(i,N){ scanf("%d %d",&x[i],&y[i]); t.push_back(y[i]); } sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); go(x); go(y); vector<pair<int,int>> P(N); rep(i,N)P[i] = make_pair(x[i],y[i]); sort(P.begin(),P.end()); segtree<mint,op,e> segb(t.size()),segd(t.size()),segbd(t.size()),segcnt(t.size()); rep(i,N){ x[i] = P[i].first; y[i] = P[i].second; } rep(i,N){ //cout<<x[i]<<','<<y[i]<<endl; mint temp = 0; int d = distance(t.begin(),lower_bound(t.begin(),t.end(),P[i].second)); //ac { mint tt = segcnt.prod(0,d); tt -= segcnt.prod(d,t.size()); tt *= x[i]; tt *= y[i]; //cout<<(-tt).val()<<endl; temp += tt; } //ad { mint tt = segd.prod(0,d); tt -= segd.prod(d,t.size()); tt *= x[i]; //cout<<(-tt).val()<<endl; temp -= tt; } //bc { mint tt = segb.prod(0,d); tt -= segb.prod(d,t.size()); tt *= y[i]; //cout<<(-tt).val()<<endl; temp -= tt; } //bd { mint tt = segbd.prod(0,d); tt -= segbd.prod(d,t.size()); temp += tt; //cout<<(-tt).val()<<endl; } ans += temp*2; segb.set(d,segb.get(d)+x[i]); segd.set(d,segd.get(d)+y[i]); segbd.set(d,segbd.get(d)+mint(x[i])*y[i]); segcnt.set(d,segcnt.get(d)+1); } cout<<ans.val()<<endl; return 0; }