結果

問題 No.1649 Manhattan Square
ユーザー merlinmerlin
提出日時 2021-08-13 23:32:27
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,064 ms / 3,000 ms
コード長 3,096 bytes
コンパイル時間 3,918 ms
コンパイル使用メモリ 76,652 KB
実行使用メモリ 113,872 KB
最終ジャッジ日時 2023-08-27 19:32:43
合計ジャッジ時間 75,742 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
49,680 KB
testcase_01 AC 42 ms
49,740 KB
testcase_02 AC 165 ms
56,572 KB
testcase_03 AC 153 ms
56,632 KB
testcase_04 AC 161 ms
55,568 KB
testcase_05 AC 147 ms
55,396 KB
testcase_06 AC 160 ms
56,144 KB
testcase_07 AC 1,960 ms
112,344 KB
testcase_08 AC 1,894 ms
111,400 KB
testcase_09 AC 1,915 ms
110,960 KB
testcase_10 AC 1,892 ms
112,532 KB
testcase_11 AC 1,913 ms
107,300 KB
testcase_12 AC 1,459 ms
89,656 KB
testcase_13 AC 1,673 ms
100,172 KB
testcase_14 AC 1,554 ms
94,536 KB
testcase_15 AC 1,631 ms
95,596 KB
testcase_16 AC 1,414 ms
88,068 KB
testcase_17 AC 1,471 ms
88,340 KB
testcase_18 AC 1,398 ms
86,936 KB
testcase_19 AC 1,603 ms
94,472 KB
testcase_20 AC 1,524 ms
90,224 KB
testcase_21 AC 1,721 ms
99,852 KB
testcase_22 AC 2,064 ms
110,528 KB
testcase_23 AC 1,787 ms
111,428 KB
testcase_24 AC 1,840 ms
113,872 KB
testcase_25 AC 1,930 ms
111,156 KB
testcase_26 AC 1,975 ms
108,864 KB
testcase_27 AC 1,919 ms
110,300 KB
testcase_28 AC 1,918 ms
106,764 KB
testcase_29 AC 1,918 ms
112,760 KB
testcase_30 AC 1,925 ms
112,828 KB
testcase_31 AC 2,038 ms
110,676 KB
testcase_32 AC 1,855 ms
112,380 KB
testcase_33 AC 1,950 ms
111,200 KB
testcase_34 AC 1,937 ms
110,876 KB
testcase_35 AC 1,904 ms
110,764 KB
testcase_36 AC 2,012 ms
105,620 KB
testcase_37 AC 1,890 ms
110,472 KB
testcase_38 AC 1,927 ms
112,580 KB
testcase_39 AC 1,928 ms
112,496 KB
testcase_40 AC 1,912 ms
110,256 KB
testcase_41 AC 1,915 ms
108,000 KB
testcase_42 AC 1,756 ms
111,728 KB
testcase_43 AC 42 ms
49,664 KB
testcase_44 AC 42 ms
49,628 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