結果

問題 No.1649 Manhattan Square
ユーザー merlinmerlin
提出日時 2021-08-13 23:32:27
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,233 ms / 3,000 ms
コード長 3,096 bytes
コンパイル時間 3,081 ms
コンパイル使用メモリ 88,516 KB
実行使用メモリ 99,004 KB
最終ジャッジ日時 2024-06-08 15:17:25
合計ジャッジ時間 78,690 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
37,236 KB
testcase_01 AC 53 ms
36,832 KB
testcase_02 AC 167 ms
42,256 KB
testcase_03 AC 162 ms
42,072 KB
testcase_04 AC 159 ms
41,920 KB
testcase_05 AC 161 ms
41,720 KB
testcase_06 AC 162 ms
41,628 KB
testcase_07 AC 2,144 ms
98,004 KB
testcase_08 AC 2,045 ms
98,060 KB
testcase_09 AC 2,041 ms
93,196 KB
testcase_10 AC 2,024 ms
97,780 KB
testcase_11 AC 2,060 ms
98,196 KB
testcase_12 AC 1,585 ms
79,436 KB
testcase_13 AC 1,903 ms
88,984 KB
testcase_14 AC 1,578 ms
79,920 KB
testcase_15 AC 1,754 ms
85,456 KB
testcase_16 AC 1,472 ms
77,532 KB
testcase_17 AC 1,446 ms
77,636 KB
testcase_18 AC 1,403 ms
75,872 KB
testcase_19 AC 1,671 ms
82,356 KB
testcase_20 AC 1,538 ms
79,844 KB
testcase_21 AC 1,810 ms
89,748 KB
testcase_22 AC 2,079 ms
98,188 KB
testcase_23 AC 2,096 ms
98,164 KB
testcase_24 AC 2,110 ms
98,128 KB
testcase_25 AC 1,995 ms
97,988 KB
testcase_26 AC 2,100 ms
98,244 KB
testcase_27 AC 2,036 ms
98,076 KB
testcase_28 AC 2,052 ms
98,256 KB
testcase_29 AC 2,028 ms
98,124 KB
testcase_30 AC 2,020 ms
97,996 KB
testcase_31 AC 2,044 ms
97,928 KB
testcase_32 AC 2,099 ms
97,888 KB
testcase_33 AC 2,233 ms
98,120 KB
testcase_34 AC 2,220 ms
98,364 KB
testcase_35 AC 1,996 ms
98,164 KB
testcase_36 AC 1,996 ms
98,028 KB
testcase_37 AC 1,963 ms
97,580 KB
testcase_38 AC 1,965 ms
98,164 KB
testcase_39 AC 1,992 ms
98,104 KB
testcase_40 AC 2,012 ms
97,900 KB
testcase_41 AC 1,984 ms
98,260 KB
testcase_42 AC 1,816 ms
99,004 KB
testcase_43 AC 53 ms
37,068 KB
testcase_44 AC 50 ms
36,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int n=Integer.parseInt(bu.readLine());
        PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]>o2[0]) return 1;
                else return -1;
            }});

        int i,a[][]=new int[n][2];
        for(i=0;i<n;i++)
        {
            String s[]=bu.readLine().split(" ");
            pq.add(new int[]{Integer.parseInt(s[0]),Integer.parseInt(s[1])});
        }

        HashMap<Integer,Integer> hm=new HashMap<>();
        ArrayList<Integer> al=new ArrayList<>();
        for(i=0;i<n;i++)
        {
            a[i]=pq.poll();
            if(hm.get(a[i][1])==null)
            {
                hm.put(a[i][1],0);
                al.add(a[i][1]);
            }
        }

        Collections.sort(al);
        i=0;
        for(int x:al) hm.put(x,i++);
        int sz=i;
        long x2=0,y2=0,sx=0,sy=0,xy[]=new long[sz+1],ox[]=new long[sz+1],oy[]=new long[sz+1],cn[]=new long[sz+1];
        long ans=0,cur,val,val2;
        for(i=0;i<n;i++)
        {
            cur=(x2+y2+1l*a[i][0]*a[i][0]%M*i%M+1l*a[i][1]*a[i][1]%M*i%M)%M;
            //x^2+y^2+a^2+b^2
            cur=(cur+(-sx*a[i][0]%M+M)%M+(-sy*a[i][1]%M+M)%M)%M;
            //-2xa-2yb
            x2=(x2+1l*a[i][0]*a[i][0]%M)%M; y2=(y2+1l*a[i][1]*a[i][1]%M)%M;
            sx=(sx+a[i][0]*2)%M; sy=(sy+a[i][1]*2)%M;

            val=query(ox,hm.get(a[i][1])); val2=query(ox,sz-1);
            cur=(cur-val*a[i][1]%M+M)%M; cur=(cur+(val2-val+M)%M*a[i][1]%M)%M;
            //-2ay for b<=y and 2ay for b>y
            val=query(oy,hm.get(a[i][1])); val2=query(oy,sz-1);
            cur=(cur-val*a[i][0]%M+M)%M; cur=(cur+(val2-val+M)%M*a[i][0]%M)%M;
            //-2bx and 2bx for b<=y && b>y resp
            val=query(xy,hm.get(a[i][1])); val2=query(xy,sz-1);
            cur=(cur+val*2-val2+M)%M;
            //2ab for b<=y and -2ab for b>y
            val=query(cn,hm.get(a[i][1])); val2=i-val;
            cur=(cur+val*2*a[i][0]%M*a[i][1]%M)%M; cur=(cur-(2l*val2*a[i][0]%M*a[i][1]%M)+M)%M;
            //2xy*k for the k values where b<=y and for rem -2xy*(tot-k)
            ans=(ans+cur)%M;

            update(ox,hm.get(a[i][1]),2*a[i][0],sz);
            update(oy,hm.get(a[i][1]),2*a[i][1],sz);
            update(xy,hm.get(a[i][1]),2l*a[i][0]*a[i][1]%M,sz);
            update(cn,hm.get(a[i][1]),1,sz);
        }
        System.out.println(ans);
    }

    static long M=998244353;
    static void update(long bit[],int i,long v,int n)
    {
        i++;
        while(i<=n)
        {
            bit[i]=(bit[i]+v)%M;
            i+=i&-i;
        }
    }

    static long query(long bit[],int i)
    {
        i++;
        long s=0;
        while(i>0)
        {
            s=(s+bit[i])%M;
            i-=i&-i;
        }
        return s;
    }
}
0