結果

問題 No.743 Segments on a Polygon
ユーザー claw88claw88
提出日時 2018-10-06 00:36:46
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 149 ms / 2,000 ms
コード長 5,322 bytes
コンパイル時間 2,125 ms
コンパイル使用メモリ 119,032 KB
実行使用メモリ 31,956 KB
最終ジャッジ日時 2024-11-14 08:04:22
合計ジャッジ時間 3,396 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
31,824 KB
testcase_01 AC 147 ms
31,956 KB
testcase_02 AC 148 ms
29,920 KB
testcase_03 AC 147 ms
29,908 KB
testcase_04 AC 148 ms
29,528 KB
testcase_05 AC 148 ms
31,700 KB
testcase_06 AC 149 ms
31,704 KB
testcase_07 AC 148 ms
27,752 KB
testcase_08 AC 148 ms
29,908 KB
testcase_09 AC 131 ms
29,140 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
//using System.Text;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
//using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    void chmax<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? b : a; }
    void chmin<T>(ref T a, T b) where T : IComparable<T> { a = a.CompareTo(b) < 0 ? a : b; }


    void swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    void solve()
    {
        int N = cin.nextint;
        int M = cin.nextint;
        //var A = new int[2 * M + 1];
        //for (int i = 0; i < N; i++)
        //{
        //    int a = cin.nextint;
        //    int b = cin.nextint;
        //    if (b < a) swap(ref a, ref b);
        //    if (b - a == 1 || b - a == M - 1)
        //    {
        //        continue;
        //    }
        //    A[a + 1]++;
        //    A[b]--;
        //    A[b + 1]++;
        //    A[a + M]--;
        //}
        //for (int i = 0; i < 2 * M; i++)
        //{
        //    A[i + 1] += A[i];
        //}
        //for (int i = 0; i < M; i++)
        //{
        //    A[i] += A[i + M];
        //}
        //WriteLine(string.Join(" ", A));
        //for (int i = 0; i < M; i++)
        //{

        //}
        var BIT2 = new FenwickTree(M);


        var A = new int[N];
        var B = new int[N];
        for (int i = 0; i < N; i++)
        {
            A[i] = cin.nextint;
            B[i] = cin.nextint;
            if (B[i] < A[i]) swap(ref A[i], ref B[i]);
        }
        //WriteLine(string.Join(" ", A));
    
        Array.Sort(A, B);

        //WriteLine(string.Join(" ", A));
        long sum = 0;
        for (int i = 0; i < N; i++)
        {
            int a = A[i] + 1;
            int b = B[i] + 1;
            sum  += BIT2[a, b];
            BIT2.Add(b, 1);
        }

        WriteLine(sum);

    }

}
#region Fenwick
public class FenwickTree
{
    int n;
    long[] bit;
    int max = 1;
    public FenwickTree(int size)
    {
        n = size; bit = new long[n + 1];
        while ((max << 1) <= n) max <<= 1;
    }
    /// <summary>sum[a,b]</summary>
    public long this[int i, int j] { get { return this[j] - this[i - 1]; } }
    /// <summary>sum[0,i]</summary>
    public long this[int i] { get { long s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } }
    public int LowerBound(long w)
    {
        if (w <= 0) return 0;
        int x = 0;
        for (int k = max; k > 0; k >>= 1)
            if (x + k <= n && bit[x + k] < w)
            {
                w -= bit[x + k];
                x += k;
            }
        return x + 1;
    }
    /// <summary>add v to bit[i]</summary>
    public void Add(int i, long v)
    {
        if (i == 0) System.Diagnostics.Debug.Fail("BIT is 1 indexed");
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    public long[] Items
    {
        get
        {
            var ret = new long[n + 1];
            for (int i = 0; i < ret.Length; i++)
                ret[i] = this[i, i];
            return ret;
        }
    }
}
#endregion
#region RangeAddFenwick
public class RangeAddFenwickTree
{
    int n;
    FenwickTree a, b;
    public RangeAddFenwickTree(int n)
    {
        this.n = n;
        a = new FenwickTree(n);
        b = new FenwickTree(n);
    }
    /// <summary>Add V to[i,j]</summary>
    public void Add(int i, int j, long v)
    {
        a.Add(i, -(i - 1) * v); a.Add(j + 1, j * v);
        b.Add(i, v); b.Add(j + 1, -v);
    }
    /// <summary>Sum [0,i]</summary>
    public long this[int i] { get { return a[i] + b[i] * i; } }
    /// <summary>Sum [i,j]</summary>
    public long this[int i, int j] { get { return this[j] - this[i - 1]; } }
    public long[] Items
    {
        get
        {
            var ret = new long[n + 1];
            for (int i = 0; i < ret.Length; i++)
                ret[i] = this[i, i];
            return ret;
        }
    }
}
#endregion
class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}
0