#1193171 (C#) No.728 ギブ and テイク

• 問題: No.728 ギブ and テイク
• ユーザー: 👑 kakel-san
• 提出日時: 2026-10-15 22:19:51
• 言語: C# (.NET 10.0.402 + ACL)
• 結果: AC
• 実行時間: 574 ms / 3,000 ms
• コード長: 4,571 bytes
• コンパイル時間: 5,179 ms
• コンパイル使用メモリ: 171,212 KB
• 実行使用メモリ: 198,268 KB
• 最終ジャッジ日時: 2026-10-15 22:20:20
• 合計ジャッジ時間: 18,385 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	AC * 3
other	AC * 30

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (168 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();
    public static void Main()
    {
        Solve();
    }
    static void Solve()
    {
        var n = NN;
        var a = NList;
        var map = NArr(n);
        var ar = new int[n];
        for (var i = 0; i < n; ++i) ar[i] = Math.Min(1_000_000_001, a[i] + map[i][1]);
        var wm = new WaveletMatrix(ar);
        var ans = 0L;
        for (var i = 1; i < n; ++i)
        {
            var pos = LowerBound(0, a[i] - map[i][0], a);
            if (pos < i)
            {
                ans += i - pos - wm.CountLower(pos, i, a[i]);
            }
        }
        WriteLine(ans);
    }
    static int LowerBound(int left, int min, IList<int> list)
    {
        if (list[left] >= min) return left;
        var ng = left;
        var ok = list.Count;
        while (ok - ng > 1)
        {
            var mid = (ng + ok) / 2;
            if (list[mid] < min) ng = mid;
            else ok = mid;
        }
        return ok;
    }
    /// <summary>
    /// WaveletMatrix 初期化時に設定した区間に対して様々な情報を取得するクエリを提供する
    /// </summary>
    class WaveletMatrix
    {
        int n;
        int height;
        int[,] m;
        public WaveletMatrix(int[] _a)
        {
            var a = (int[])_a.Clone();
            n = a.Length;
            var max = 0;
            for (var i = 0; i < n; ++i) max = Math.Max(max, a[i]);
            height = 0;
            var tmp = max;
            while (tmp > 0)
            {
                ++height;
                tmp >>= 1;
            }
            if (height == 0) ++height;
            m = new int[height, n + 1];
            for (var h = height - 1; h >= 0; --h)
            {
                var dir = new List<int>(n);
                var left = new List<int>();
                var right = new List<int>();
                for (var i = 0; i < n; ++i)
                {
                    dir.Add((a[i] >> h) & 1);
                    if (dir[i] == 0) left.Add(a[i]);
                    else right.Add(a[i]);
                }
                for (var i = 0; i < left.Count; ++i) a[i] = left[i];
                for (var i = 0; i < right.Count; ++i) a[i + left.Count] = right[i];
                for (var i = 0; i < n; ++i) m[h, i + 1] = m[h, i] + dir[i];
            }
        }
        (int l0, int r0, int l1, int r1) SubtreeRange(int h, int l, int r)
        {
            var l0 = l - m[h, l];
            var l1 = m[h, l];
            var r0 = r - m[h, r];
            var r1 = m[h, r];
            var c0 = n - m[h, n];
            return (l0, r0, c0 + l1, c0 + r1);
        }
        /// <summary>区間[l,r)からk番目に小さい値を返す kは0-indexed</summary>
        public int KthSmall(int l, int r, int k)
        {
            if (r - l <= k) return -1;
            var ans = 0;
            for (var h = height - 1; h >= 0; --h)
            {
                var one = m[h, r] - m[h, l];
                var zero = r - l - one;
                var (l0, r0, l1, r1) = SubtreeRange(h, l, r);
                ans <<= 1;
                if (zero <= k)
                {
                    l = l1;
                    r = r1;
                    k -= zero;
                    ++ans;
                }
                else
                {
                    l = l0;
                    r = r0;
                }
            }
            return ans;
        }
        /// <summary>区間[l,r)からx未満の値の個数を返す</summary>
        public int CountLower(int l, int r, int x)
        {
            if ((x >> height) != 0) return n;
            var ans = 0;
            for (var h = height - 1; h >= 0; --h)
            {
                var (l0, r0, l1, r1) = SubtreeRange(h, l, r);
                if (((x >> h) & 1) == 0)
                {
                    l = l0;
                    r = r0;
                }
                else
                {
                    l = l1;
                    r = r1;
                    ans += r0 - l0;
                }
            }
            return ans;
        }
    }
}