AtCoderのContest14の問題Dの回答例（ただしどっちにせよ速度足りない） http://arc014.contest.atcoder.jp/tasks/arc014_4

Array.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder {
    class Cont014_4 {
        static void Main(string[] args) {
            string fst = Console.ReadLine();
            var fsts = fst.Split(' ');
            long all = long.Parse(fsts[0]);
            int n = int.Parse(fsts[1]);
            int m = int.Parse(fsts[2]);

            var ls = new List<long>(n);
            string line;
            for(int i=0; i<n; ++i) {
                line = Console.ReadLine();
                ls.Add(long.Parse(line));
            }
            var ranges = new List<Tuple<int, int>>(n);
            while((line = Console.ReadLine()) != null) {
                var xs = line.Split(' ');
                int x = int.Parse(xs[0]);
                int y = int.Parse(xs[1]);
                ranges.Add(Tuple.Create(x, y));
            }
            List<int> result = Exec(all, ls.OrderBy(x=>x).Distinct().ToArray(), ranges);
            foreach(int count in result) Console.WriteLine(count);
        }

        static List<int> Exec(
            long all,
            long[] lines,    // Require Sorted
            List<Tuple<int, int>> ranges
            ) {
            var result = new List<int>(ranges.Count);
            foreach(var range in ranges) {
                result.Add(Elem(all, lines, range));
            }
            return result;
        }

        static int Elem(long all, long[] lines, Tuple<int, int> range) {
            long last = 1;
            int count = 0;
            foreach(long l in lines) {
                long left = Math.Max(l - range.Item1, last);
                long right = Math.Min(l + range.Item2, all);
                last = right + 1;
                count += (int)(right - left + 1);
            }
            return count;
        }
    }
}

List.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder {
    class Cont014_4 {
        static void Main(string[] args) {
            string fst = Console.ReadLine();
            var fsts = fst.Split(' ');
            long all = long.Parse(fsts[0]);
            int n = int.Parse(fsts[1]);
            int m = int.Parse(fsts[2]);

            var ls = new List<long>(n);
            string line;
            for(int i=0; i<n; ++i) {
                line = Console.ReadLine();
                ls.Add(long.Parse(line));
            }
            var ranges = new List<Tuple<int, int>>(n);
            while((line = Console.ReadLine()) != null) {
                var xs = line.Split(' ');
                int x = int.Parse(xs[0]);
                int y = int.Parse(xs[1]);
                ranges.Add(Tuple.Create(x, y));
            }
            List<int> result = Exec(all, ls.OrderBy(x=>x).Distinct().ToList(), ranges);
            foreach(int count in result) Console.WriteLine(count);
        }

        static List<int> Exec(
            long all,
            List<long> lines,    // Require Sorted
            List<Tuple<int, int>> ranges
            ) {
            var result = new List<int>(ranges.Count);
            foreach(var range in ranges) {
                result.Add(Elem(all, lines, range));
            }
            return result;
        }

        static int Elem(long all, List<long> lines, Tuple<int, int> range) {
            long last = 1;
            int count = 0;
            foreach(long l in lines) {
                long left = Math.Max(l - range.Item1, last);
                long right = Math.Min(l + range.Item2, all);
                last = right + 1;
                count += (int)(right - left + 1);
            }
            return count;
        }
    }
}