結果
問題 | No.1649 Manhattan Square |
ユーザー |
|
提出日時 | 2021-08-13 22:17:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 465 ms / 3,000 ms |
コード長 | 1,042 bytes |
コンパイル時間 | 1,077 ms |
コンパイル使用メモリ | 87,292 KB |
実行使用メモリ | 8,832 KB |
最終ジャッジ日時 | 2024-10-03 19:44:39 |
合計ジャッジ時間 | 18,656 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 9 | main() | ^~~~
ソースコード
#include<iostream> #include<algorithm> #include<atcoder/modint> #include<atcoder/fenwicktree> using namespace std; using mint=atcoder::modint998244353; int N; pair<int,int>XY[2<<17]; main() { cin>>N; mint ans=0; mint sx=0,sy=0; for(int i=0;i<N;i++) { cin>>XY[i].first>>XY[i].second; mint x=XY[i].first,y=XY[i].second; ans+=(x*x+y*y)*(N-1); ans-=2*sx*x+2*sy*y; sx+=x; sy+=y; } for(int _=0;_<2;_++) { mint now=0; vector<int>ys(N); for(int i=0;i<N;i++) { ys[i]=XY[i].second=(int)1e9-XY[i].second; } sort(XY,XY+N); sort(ys.begin(),ys.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end()); atcoder::fenwick_tree<mint>cnt(ys.size()),xy(ys.size()),Sx(ys.size()),Sy(ys.size()); for(int i=0;i<N;i++) { int yi=lower_bound(ys.begin(),ys.end(),XY[i].second)-ys.begin(); mint x=XY[i].first,y=XY[i].second; now+=xy.sum(0,yi)+cnt.sum(0,yi)*x*y; now-=Sx.sum(0,yi)*y+Sy.sum(0,yi)*x; xy.add(yi,x*y); cnt.add(yi,1); Sx.add(yi,x); Sy.add(yi,y); } ans+=2*now; } cout<<ans.val()<<endl; }