結果
| 問題 |
No.1698 Face to Face
|
| ユーザー |
 eSeF
|
| 提出日時 | 2021-08-28 02:12:24 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,004 ms / 5,000 ms |
| コード長 | 13,245 bytes |
| コンパイル時間 | 8,344 ms |
| コンパイル使用メモリ | 173,052 KB |
| 実行使用メモリ | 258,364 KB |
| 最終ジャッジ日時 | 2024-07-19 09:48:40 |
| 合計ジャッジ時間 | 31,437 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (101 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/
ソースコード
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; _ < 18; _++)
{
// 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;
}
}
}