結果
問題 | No.1649 Manhattan Square |
ユーザー | 沙耶花 |
提出日時 | 2021-08-13 22:35:25 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 429 ms / 3,000 ms |
コード長 | 1,860 bytes |
コンパイル時間 | 5,332 ms |
コンパイル使用メモリ | 267,912 KB |
実行使用メモリ | 16,508 KB |
最終ジャッジ日時 | 2024-04-14 18:56:31 |
合計ジャッジ時間 | 22,531 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 6 ms
6,940 KB |
testcase_03 | AC | 5 ms
6,940 KB |
testcase_04 | AC | 5 ms
6,940 KB |
testcase_05 | AC | 6 ms
6,944 KB |
testcase_06 | AC | 6 ms
6,940 KB |
testcase_07 | AC | 409 ms
16,236 KB |
testcase_08 | AC | 393 ms
16,360 KB |
testcase_09 | AC | 410 ms
16,240 KB |
testcase_10 | AC | 410 ms
16,240 KB |
testcase_11 | AC | 398 ms
16,364 KB |
testcase_12 | AC | 338 ms
9,592 KB |
testcase_13 | AC | 371 ms
12,132 KB |
testcase_14 | AC | 365 ms
12,280 KB |
testcase_15 | AC | 370 ms
12,152 KB |
testcase_16 | AC | 335 ms
9,724 KB |
testcase_17 | AC | 333 ms
9,464 KB |
testcase_18 | AC | 320 ms
8,440 KB |
testcase_19 | AC | 363 ms
12,284 KB |
testcase_20 | AC | 346 ms
9,848 KB |
testcase_21 | AC | 364 ms
12,152 KB |
testcase_22 | AC | 414 ms
16,376 KB |
testcase_23 | AC | 418 ms
16,248 KB |
testcase_24 | AC | 405 ms
16,376 KB |
testcase_25 | AC | 414 ms
16,184 KB |
testcase_26 | AC | 409 ms
16,376 KB |
testcase_27 | AC | 421 ms
16,372 KB |
testcase_28 | AC | 416 ms
16,376 KB |
testcase_29 | AC | 416 ms
16,248 KB |
testcase_30 | AC | 422 ms
16,372 KB |
testcase_31 | AC | 416 ms
16,376 KB |
testcase_32 | AC | 419 ms
16,376 KB |
testcase_33 | AC | 407 ms
16,508 KB |
testcase_34 | AC | 425 ms
16,248 KB |
testcase_35 | AC | 416 ms
16,244 KB |
testcase_36 | AC | 421 ms
16,248 KB |
testcase_37 | AC | 420 ms
16,244 KB |
testcase_38 | AC | 419 ms
16,248 KB |
testcase_39 | AC | 429 ms
16,372 KB |
testcase_40 | AC | 415 ms
16,252 KB |
testcase_41 | AC | 426 ms
16,372 KB |
testcase_42 | AC | 280 ms
16,252 KB |
testcase_43 | AC | 2 ms
6,940 KB |
testcase_44 | AC | 2 ms
6,940 KB |
ソースコード
#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; }