結果

問題 No.1698 Face to Face
ユーザー eSeFeSeF
提出日時 2021-08-29 17:56:44
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 859 ms / 5,000 ms
コード長 13,245 bytes
コンパイル時間 8,604 ms
コンパイル使用メモリ 170,100 KB
実行使用メモリ 258,040 KB
最終ジャッジ日時 2024-07-19 09:52:29
合計ジャッジ時間 30,257 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
30,720 KB
testcase_01 AC 55 ms
30,720 KB
testcase_02 AC 57 ms
30,976 KB
testcase_03 AC 513 ms
89,088 KB
testcase_04 AC 541 ms
93,312 KB
testcase_05 AC 704 ms
102,604 KB
testcase_06 AC 680 ms
103,296 KB
testcase_07 AC 690 ms
108,388 KB
testcase_08 AC 668 ms
103,504 KB
testcase_09 AC 677 ms
103,680 KB
testcase_10 AC 531 ms
103,168 KB
testcase_11 AC 730 ms
100,788 KB
testcase_12 AC 812 ms
107,208 KB
testcase_13 AC 58 ms
30,848 KB
testcase_14 AC 57 ms
31,104 KB
testcase_15 AC 855 ms
89,440 KB
testcase_16 AC 844 ms
89,472 KB
testcase_17 AC 838 ms
89,212 KB
testcase_18 AC 734 ms
92,160 KB
testcase_19 AC 726 ms
91,392 KB
testcase_20 AC 686 ms
77,284 KB
testcase_21 AC 397 ms
54,272 KB
testcase_22 AC 309 ms
49,024 KB
testcase_23 AC 132 ms
41,984 KB
testcase_24 AC 492 ms
64,776 KB
testcase_25 AC 859 ms
80,640 KB
testcase_26 AC 108 ms
38,784 KB
testcase_27 AC 226 ms
46,728 KB
testcase_28 AC 243 ms
45,952 KB
testcase_29 AC 193 ms
49,024 KB
testcase_30 AC 482 ms
70,588 KB
testcase_31 AC 356 ms
54,016 KB
testcase_32 AC 602 ms
68,608 KB
testcase_33 AC 592 ms
72,556 KB
testcase_34 AC 819 ms
90,112 KB
testcase_35 AC 56 ms
30,976 KB
testcase_36 AC 57 ms
30,976 KB
testcase_37 AC 55 ms
30,848 KB
testcase_38 AC 56 ms
30,720 KB
testcase_39 AC 55 ms
30,556 KB
testcase_40 AC 56 ms
31,104 KB
testcase_41 AC 56 ms
30,720 KB
testcase_42 AC 56 ms
30,848 KB
testcase_43 AC 55 ms
30,848 KB
testcase_44 AC 58 ms
30,848 KB
testcase_45 AC 603 ms
93,108 KB
testcase_46 AC 580 ms
94,076 KB
testcase_47 AC 739 ms
258,040 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (103 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Numerics;
using System.Threading;
using System.Runtime.InteropServices;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using static System.Math;
using static System.Array;
using static AtCoder.Cout;
using static AtCoder.Tool;
namespace AtCoder
{
    class AC
    {
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 3;
        static readonly int[] dI = { 0, 1, 0, -1, 1, -1, -1, 1 };
        static readonly int[] dJ = { 1, 0, -1, 0, 1, 1, -1, -1 };
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw);

            /*var th = new Thread(Run, 1 << 26);
            th.Start();
            th.Join();*/

            Run();
            Console.Out.Flush();
        }
        static void Run()
        {
            int Testcase = 1;
            //Testcase = Cin.Int;
            for (var testcase_id = 0; testcase_id < Testcase; testcase_id++)
            {
                Solve(testcase_id);
            }
        }
        static void Solve(int testcase_id)
        {
            int N = Cin.Int;
            var A = Cin.ReadSplitInt;
            var B = Cin.ReadSplitInt;
            var Z = Cin.ReadSplitInt;
            var ida = new int[N];
            var idb = new int[N];
            for(var i = 0; i < N; i++)
            {
                A[i]--;B[i]--;
                Z[i]--;
                ida[A[i]] = i;
                idb[B[i]] = i;
            }

            //並列二分探索

            var pos_left = new int[N];
            var l = new int[N];
            var r = new int[N];
            for(var i = 0; i < N; i++)
            {
                l[i] = -1;r[i] = N;
            }
            var mid = new Queue<int>[N];
            for (var i = 0; i < N; i++) mid[i] = new Queue<int>();

            for(var _ = 0; _ < 17; _++)
            {
                // mid[i] : k = i で判定を行うペア番号の集合
                for (var i = 0; i < N; i++)
                    if (r[i] - l[i] > 1) mid[(l[i] + r[i]) / 2].Enqueue(i);
                var ufa = new DSU_AB(N);
                var ufb = new DSU_AB(N);
                for (var k = 0; k < N; k++)
                {
                    int ia = ida[k], ib = idb[k];
                    if (0 < ia && A[ia - 1] <= k) ufa.Unite(ia - 1, ia);
                    if (ia + 1 < N && A[ia + 1] <= k) ufa.Unite(ia, ia + 1);
                    if (0 < ib && B[ib - 1] <= k) ufb.Unite(ib - 1, ib);
                    if (ib + 1 < N && B[ib + 1] <= k) ufb.Unite(ib, ib + 1);

                    while(mid[k].Any())
                    {
                        int j = mid[k].Dequeue();
                        //この k の値において (j, Z_j) を同じ位置に配置することはできるか？
                        if (ufa.Right(ida[j]) < ufb.Left(idb[Z[j]]) || ufb.Right(idb[Z[j]]) < ufa.Left(ida[j]))
                        {
                            l[j] = k;
                        }
                        else
                        {
                            r[j] = k;
                            pos_left[j] = Max(ufa.Left(ida[j]), ufb.Left(idb[Z[j]]));
                        }
                    }
                }
            }
            for (var i = 0; i < N; i++) mid[r[i]].Enqueue(i);

            //答えを求める

            var ufi = new DSU_Idx(N);
            var less_k = new int[N];
            for(var k = 0; k < N; k++)
            {
                int ia = ida[k], ib = idb[k];
                less_k[ia]++;less_k[ib]++;
                if (less_k[ia] == 2)
                {
                    if (0 < ia && less_k[ia - 1] == 2) ufi.Unite(ia - 1, ia);
                    if (ia + 1 < N && less_k[ia + 1] == 2) ufi.Unite(ia, ia + 1);
                }
                if (less_k[ib] == 2)
                {
                    if (0 < ib && less_k[ib - 1] == 2) ufi.Unite(ib - 1, ib);
                    if (ib + 1 < N && less_k[ib + 1] == 2) ufi.Unite(ib, ib + 1);
                }

                foreach(var i in mid[k])
                {
                    ufi.Add_Pair(pos_left[i]);
                }

                OutL(ufi.Score);
            }
        }
    }
    public class DSU_AB
    {
        private int n;
        private int[] par_size;
        private int[] left;
        private int[] right;
        // par_size[i] = sizeof(i) (par_size[i] <  0)
        //               parent(i) (par_size[i] >= 0)
        public DSU_AB(int size)
        {
            n = size;
            par_size = new int[n];
            left = new int[n];
            right = new int[n];
            for (var i = 0; i < n; i++)
            {
                par_size[i] = -1;
                left[i] = right[i] = i;
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Root(int v)
        {
            if (par_size[v] < 0) return v;
            while (par_size[par_size[v]] >= 0)
            {
                (v, par_size[v]) = (par_size[v], par_size[par_size[v]]);
            }
            return par_size[v];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int SizeOf(int v) => -par_size[Root(v)];

        public void Unite(int u, int v)
        {
            int ru = Root(u), rv = Root(v);
            if (ru == rv) return;
            if (par_size[ru] > par_size[rv])
            {
                par_size[rv] += par_size[ru];
                par_size[ru] = rv;

                left[rv] = Min(left[rv], left[ru]);
                right[rv] = Max(right[rv], right[ru]);
            }
            else
            {
                par_size[ru] += par_size[rv];
                par_size[rv] = ru;

                left[ru] = Min(left[ru], left[rv]);
                right[ru] = Max(right[ru], right[rv]);
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Same(int u, int v) => Root(u) == Root(v);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Left(int v) => left[Root(v)];
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Right(int v) => right[Root(v)];

    }
    public class DSU_Idx
    {
        private int n;
        private int[] par_size;
        private int[] num_pair;
        public int Score;
        // par_size[i] = sizeof(i) (par_size[i] <  0)
        //               parent(i) (par_size[i] >= 0)
        public DSU_Idx(int size)
        {
            n = size;
            par_size = new int[n];
            num_pair = new int[n];
            Score = 0;
            for (var i = 0; i < n; i++)
            {
                par_size[i] = -1;
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Root(int v)
        {
            if (par_size[v] < 0) return v;
            while (par_size[par_size[v]] >= 0)
            {
                (v, par_size[v]) = (par_size[v], par_size[par_size[v]]);
            }
            return par_size[v];
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int SizeOf(int v) => -par_size[Root(v)];
        // unite, num_pair更新時にScoreを差分更新する
        public void Unite(int u, int v)
        {
            int ru = Root(u), rv = Root(v);
            if (ru == rv) return;

            Score -= (Sub_score(ru) + Sub_score(rv));

            if (par_size[ru] > par_size[rv])
            {
                par_size[rv] += par_size[ru];
                par_size[ru] = rv;

                num_pair[rv] += num_pair[ru];
                Score += Sub_score(rv);
            }
            else
            {
                par_size[ru] += par_size[rv];
                par_size[rv] = ru;

                num_pair[ru] += num_pair[rv];
                Score += Sub_score(ru);
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Add_Pair(int v)
        {
            Score -= Sub_score(v);
            num_pair[Root(v)]++;
            Score += Sub_score(v);
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public int Sub_score(int v) => Min(-par_size[Root(v)], num_pair[Root(v)]);
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Same(int u, int v) => Root(u) == Root(v);

    }
    static class Cin
    {
        public static string[] ReadSplit => Console.ReadLine().Split();
        public static int[] ReadSplitInt => ConvertAll(ReadSplit, int.Parse);
        public static long[] ReadSplitLong => ConvertAll(ReadSplit, long.Parse);
        public static double[] ReadSplit_Double => ConvertAll(ReadSplit, double.Parse);
        public static string Str => Console.ReadLine();
        public static int Int => int.Parse(Console.ReadLine());
        public static long Long => long.Parse(Console.ReadLine());
        public static double Double => double.Parse(Console.ReadLine());
        public static T Conv<T>(string input)
        {
            return (T)Convert.ChangeType(input, typeof(T));
        }
        public static void Scanf<T>(out T a) => a = Conv<T>(Console.ReadLine());
        public static void Scanf<T, U>(out T a, out U b)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); }
        public static void Scanf<T, U, V>(out T a, out U b, out V c)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); }
        public static void Scanf<T, U, V, W>(out T a, out U b, out V c, out W d)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); }
        public static void Scanf<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e)
        { var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); e = Conv<X>(q[4]); }
    }
    static class Cout
    {
        public static void OutL(object s) => Console.WriteLine(s);
        public static void Out_Sep<T>(IEnumerable<T> s) => Console.WriteLine(string.Join(" ", s));
        public static void Out_Sep<T>(IEnumerable<T> s, string sep) => Console.WriteLine(string.Join($"{sep}", s));
        public static void Out_Sep(params object[] s) => Console.WriteLine(string.Join(" ", s));
        public static void Out_One(object s) => Console.Write($"{s} ");
        public static void Out_One(object s, string sep) => Console.Write($"{s}{sep}");
        public static void Endl() => Console.WriteLine();
    }
    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            array = ConvertAll(array, x => initialvalue);
        }
        static public void Swap<T>(ref T a, ref T b)
        {
            T keep = a;
            a = b;
            b = keep;
        }
        static public void Display<T>(T[,] array2d, int n, int m)
        {
            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < m; j++)
                {
                    Console.Write($"{array2d[i, j]} ");
                }
                Console.WriteLine();
            }
        }
        static public int GcdI(int a, int b)
        {
            if (a == 0 || b == 0) return Max(a, b);
            return a % b == 0 ? b : GcdI(b, a % b);
        }
        static public long Gcd(long a, long b)
        {
            if (a == 0 || b == 0) return Max(a, b);
            return a % b == 0 ? b : Gcd(b, a % b);
        }
        static public long Lcm(long a, long b) => a / Gcd(a, b) * b;
        static public int LcmI(int a, int b) => (a == 0 || b == 0) ? Max(a, b) : a / GcdI(a, b) * b;
        static public long ExtGcd(long a, long b, ref long x, ref long y)
        {
            // ax + by = gcd(a,b) なる x,y を求める // return gcd(a,b)
            if (b == 0)
            {
                x = 1; y = 0;
                return a;
            }
            long d = ExtGcd(b, a % b, ref y, ref x);
            y -= a / b * x;
            return d;
        }
        static public long LPow(int a, int b) => (long)Pow(a, b);
        static public bool Bit(long x, int dig) => ((1L << dig) & x) != 0;
        static public int Sig(long a) => a == 0 ? 0 : (int)(a / Abs(a));
        static public long F_mp(long x, long n, long mod) => n == 0 ? (1 % mod) : (n % 2 == 0 ? F_mp((x * x) % mod, n >> 1, mod) : (x * F_mp(x, n - 1, mod)) % mod);
        static public long F_inv(long x, long mod) => F_mp(x, mod - 2, mod);
        static public decimal DSqrt(decimal x, decimal epsilon = 0.0M)
        {
            if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");

            decimal current = (decimal)Math.Sqrt((double)x), previous;
            do
            {
                previous = current;
                if (previous == 0.0M) return 0;
                current = (previous + x / previous) / 2;
            }
            while (Math.Abs(previous - current) > epsilon);
            return current;
        }
    }
}
0