結果
問題 | No.743 Segments on a Polygon |
ユーザー | claw88 |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 157 ms
31,332 KB |
testcase_01 | AC | 160 ms
31,448 KB |
testcase_02 | AC | 158 ms
29,412 KB |
testcase_03 | AC | 157 ms
33,248 KB |
testcase_04 | AC | 155 ms
33,516 KB |
testcase_05 | AC | 156 ms
33,504 KB |
testcase_06 | AC | 156 ms
31,200 KB |
testcase_07 | AC | 157 ms
33,376 KB |
testcase_08 | AC | 156 ms
33,376 KB |
testcase_09 | AC | 135 ms
29,916 KB |
コンパイルメッセージ
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 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); } } }