結果
問題 | No.1649 Manhattan Square |
ユーザー | 蜜蜂 |
提出日時 | 2021-07-28 22:24:00 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 859 ms / 3,000 ms |
コード長 | 3,262 bytes |
コンパイル時間 | 4,810 ms |
コンパイル使用メモリ | 249,360 KB |
実行使用メモリ | 58,388 KB |
最終ジャッジ日時 | 2023-07-27 02:41:30 |
合計ジャッジ時間 | 35,259 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 7 ms
4,380 KB |
testcase_03 | AC | 6 ms
4,380 KB |
testcase_04 | AC | 6 ms
4,376 KB |
testcase_05 | AC | 6 ms
4,376 KB |
testcase_06 | AC | 6 ms
4,380 KB |
testcase_07 | AC | 808 ms
58,256 KB |
testcase_08 | AC | 831 ms
58,096 KB |
testcase_09 | AC | 852 ms
57,920 KB |
testcase_10 | AC | 833 ms
57,948 KB |
testcase_11 | AC | 859 ms
58,144 KB |
testcase_12 | AC | 704 ms
41,232 KB |
testcase_13 | AC | 705 ms
42,028 KB |
testcase_14 | AC | 676 ms
43,008 KB |
testcase_15 | AC | 702 ms
44,468 KB |
testcase_16 | AC | 584 ms
37,416 KB |
testcase_17 | AC | 634 ms
41,352 KB |
testcase_18 | AC | 468 ms
32,016 KB |
testcase_19 | AC | 612 ms
38,228 KB |
testcase_20 | AC | 604 ms
38,752 KB |
testcase_21 | AC | 693 ms
46,316 KB |
testcase_22 | AC | 788 ms
58,196 KB |
testcase_23 | AC | 806 ms
58,260 KB |
testcase_24 | AC | 787 ms
58,140 KB |
testcase_25 | AC | 825 ms
58,252 KB |
testcase_26 | AC | 751 ms
58,148 KB |
testcase_27 | AC | 760 ms
58,116 KB |
testcase_28 | AC | 783 ms
58,120 KB |
testcase_29 | AC | 811 ms
58,188 KB |
testcase_30 | AC | 824 ms
58,124 KB |
testcase_31 | AC | 794 ms
58,324 KB |
testcase_32 | AC | 790 ms
58,252 KB |
testcase_33 | AC | 792 ms
58,136 KB |
testcase_34 | AC | 806 ms
58,264 KB |
testcase_35 | AC | 792 ms
58,248 KB |
testcase_36 | AC | 800 ms
58,252 KB |
testcase_37 | AC | 790 ms
58,388 KB |
testcase_38 | AC | 801 ms
58,220 KB |
testcase_39 | AC | 810 ms
58,256 KB |
testcase_40 | AC | 848 ms
58,256 KB |
testcase_41 | AC | 845 ms
58,268 KB |
testcase_42 | AC | 439 ms
41,252 KB |
testcase_43 | AC | 2 ms
4,376 KB |
testcase_44 | AC | 2 ms
4,380 KB |
ソースコード
//g++ 3.cpp -std=c++14 -O2 -I . #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vll = vector<ll>; using vvll = vector<vll>; using vld = vector<ld>; using vvld = vector<vld>; #define fi first #define se second #define pb push_back #define pq_big(T) priority_queue<T,vector<T>,less<T>> #define pq_small(T) priority_queue<T,vector<T>,greater<T>> #define all(a) a.begin(),a.end() #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++) #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--) using mint = modint998244353; struct S{ //y=i範囲の点の数,xの合計,yの合計,xyの合計 int quant; mint sum_x; mint sum_y; mint sum_pro; }; S op(S a,S b){ return {a.quant+b.quant,a.sum_x+b.sum_x,a.sum_y+b.sum_y,a.sum_pro+b.sum_pro}; } S e(){ return {0,0,0,0}; } //i = 0 to N-1 j = i+1 to N (a[i]-a[j])^2 mint sum_differ(vll &a){ int sz=a.size(); mint res=0,sum=0; rep(i,0,sz){ sum+=a[i]; mint x=a[i]*a[i]; x*=2*sz; res+=x; } sum*=sum; res-=2*sum; res/=2; return res; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vll x(n),y(n); vll val_x,val_y; rep(i,0,n){ cin>>x[i]>>y[i]; val_x.pb(x[i]); val_y.pb(y[i]); } sort(all(val_x)); sort(all(val_y)); unique(all(val_x)); unique(all(val_y)); map<ll,int> inv_x; map<ll,int> inv_y; rep(i,0,val_x.size()){ inv_x[val_x[i]]=i; } rep(i,0,val_y.size()){ inv_y[val_y[i]]=i; } //座圧後の点 vector<pair<int,int>> point(n); rep(i,0,n){ point[i].fi=inv_x[x[i]]; point[i].se=inv_y[y[i]]; } sort(all(point)); //x_coordinate[i] := 座圧後にx座標がiとなる点の番号 vvi x_coordinate(n+100); rep(i,0,n){ x_coordinate[point[i].fi].pb(i); } mint ans=0; //左から平面走査 //seg[i] := 座圧後にy座標がiとなる点についてのいろいろ segtree<S,op,e> seg(n+100); rep(i,0,n+100){ if(x_coordinate[i].size()==0)continue; //寄与の計算と更新 for(int num:x_coordinate[i]){ int x=point[num].fi,y=point[num].se; mint ori_x=val_x[x],ori_y=val_y[y]; S range=seg.prod(0,y); ans+=range.quant*ori_x*ori_y; ans-=ori_x*range.sum_y; ans-=ori_y*range.sum_x; ans+=range.sum_pro; S now=seg.get(y); now.quant++; now.sum_x+=ori_x; now.sum_y+=ori_y; now.sum_pro+=ori_x*ori_y; seg.set(y,now); } } //初期化 rep(i,0,n+100){ seg.set(i,e()); } //右から平面走査 per(i,n+99,0){ if(x_coordinate[i].size()==0)continue; //寄与の計算と更新 for(int num:x_coordinate[i]){ int x=point[num].fi,y=point[num].se; mint ori_x=val_x[x],ori_y=val_y[y]; S range=seg.prod(0,y); ans-=range.quant*ori_x*ori_y; ans+=ori_x*range.sum_y; ans+=ori_y*range.sum_x; ans-=range.sum_pro; S now=seg.get(y); now.quant++; now.sum_x+=ori_x; now.sum_y+=ori_y; now.sum_pro+=ori_x*ori_y; seg.set(y,now); } } ans*=2; ans+=sum_differ(x); ans+=sum_differ(y); cout<<ans.val()<<"\n"; }