結果

問題 No.3054 Modulo Inequalities
ユーザー suisen
提出日時 2025-02-02 13:21:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,497 ms / 2,500 ms
コード長 1,753 bytes
コンパイル時間 575 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 160,116 KB
最終ジャッジ日時 2025-02-02 13:32:35
合計ジャッジ時間 36,102 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/submissions/1039531 を PyPy に移植

n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
M = 1_000_000

ini = [0] * (M * 2 + 10)
for a, b in ab:
    ini[a + M] += 1
    ini[b + M] -= 1
    ini[a - b + M] -= 1

acc = [0] * (len(ini) + 1)
for i in range(len(ini)):
    acc[i + 1] = acc[i] + ini[i]

def get_sum(l: int, r: int) -> int:
    if len(ini) < l or r < 0 or l > r:
        return 0
    return acc[min(r, len(ini))] - acc[max(l, 0)]

fs = [0] * (M + 2)
for m in range(2, M + 2):
    for st in range(0, M + 1, m):
        en = st + m
        we = st // m
        fs[m] += (get_sum(st + M, en + M)) * we
        fs[m] += (get_sum(-en + M, -st + M)) * (-we - 1)

argmax = 1
maxval = fs[1]
for i in range(2, M + 2):
    if fs[i] > maxval:
        maxval = fs[i]
        argmax = i
print(argmax)

#   registerValidation();//testlib使用時のおまじない
#   ll N = inf.readLong(1LL,500000LL,"n");//1~500000か
#   inf.readEoln();//改行か
#   vpll ab(N);
#   rep(i,0,N-1){
#     ll A = inf.readLong(1LL,1000000LL,"A");//1~1000000か
#     inf.readSpace();//spaceか
#     ll B = inf.readLong(1LL,1000000LL,"B");//1~1000000か
#     inf.readEoln();//改行か
#     ab[i]={A,B};
#   }
#   inf.readEof();//ファイル終端か

#   //auto N=cin1<ll>();
#   //auto ab=cinv<pair<ll,ll>>(N);
#   ll M=1000000;

#   vll ini(M*2+10);
#   for(auto&&[a,b]:ab){
#     ini[a+M]++;
#     ini[b+M]--;
#     ini[a-b+M]--;
#   }
#   cumulativesum cm(ini);

#   vll fs(M+2);
#   rep(m,2,M+1){
#     rep(st,0,M,m){
#       ll en=st+m;
#       ll we=st/m;
#       fs[m]+=cm(st+M,en-1+M)*we;
#       fs[m]+=cm(-en+M,-st-1+M)*(-we-1);
#     }
#   }

#   ll ans=MaxI(fs,1,M+1);
#   cout << ans << '\n';

#   return;
0