結果

問題 No.1649 Manhattan Square
ユーザー merlin
提出日時 2021-08-13 23:32:27
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,372 ms / 3,000 ms
コード長 3,096 bytes
コンパイル時間 2,802 ms
コンパイル使用メモリ 81,416 KB
実行使用メモリ 98,848 KB
最終ジャッジ日時 2024-12-28 01:31:30
合計ジャッジ時間 84,741 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

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