結果
問題 | No.743 Segments on a Polygon |
ユーザー |
|
提出日時 | 2018-10-06 00:36:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 5,547 bytes |
コンパイル時間 | 2,814 ms |
コンパイル使用メモリ | 114,320 KB |
実行使用メモリ | 33,516 KB |
最終ジャッジ日時 | 2024-11-14 08:04:15 |
合計ジャッジ時間 | 3,540 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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 BIT1 = new FenwickTree(M);var BIT2 = new FenwickTree(M);var BIT3 = new FenwickTree(2 * M);var BIT4 = new FenwickTree(2 * 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];// WriteLine($"{a} {b} {BIT1[a, b]} {BIT2[a, b]} {sum}");BIT1.Add(a, 1);BIT2.Add(b, 1);}WriteLine(sum);}}#region Fenwickpublic 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 RangeAddFenwickpublic 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;}}}#endregionclass 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); } }}