結果
| 問題 | No.618 labo-index |
| ユーザー |
 くれちー
|
| 提出日時 | 2017-12-18 01:23:41 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 23,997 bytes |
| コンパイル時間 | 1,250 ms |
| コンパイル使用メモリ | 127,996 KB |
| 実行使用メモリ | 43,068 KB |
| 最終ジャッジ日時 | 2024-05-09 11:13:22 |
| 合計ジャッジ時間 | 8,499 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 37 ms
24,248 KB |
| testcase_01 | AC | 40 ms
26,476 KB |
| testcase_02 | AC | 36 ms
23,984 KB |
| testcase_03 | AC | 41 ms
26,220 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | AC | 1,215 ms
43,068 KB |
| testcase_35 | AC | 1,239 ms
41,020 KB |
| testcase_36 | AC | 542 ms
37,820 KB |
| testcase_37 | WA | - |
| testcase_38 | AC | 37 ms
26,348 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;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Math;
using static Extensions;
using static MathExtensions;
public static class Program
{
public static void Solve()
{
var q = I;
var (t, x) = Repeat(q, () => (I, L)).ToArray().Unzip();
var ct2x = new CoordinateCompressor<long>(x.Where((y, i) => t[i] == 2));
var il = new long[q];
var sl = new SkipList<long>();
var p = 0L;
try
{
Repeat(q, i =>
{
if (t[i] == 1)
{
il[i] = x[i] - p;
var idx = sl.Count == 0 ? 0
: sl.Count == 1 ? (x[i] - p < sl[0] ? 0 : 1)
: sl.UpperBound(x[i] - p);
sl.Insert(idx, x[i] - p);
}
else if (t[i] == 2)
{
sl.RemoveAt(sl.LowerBound(il[ct2x.Compress(x[i]) + 1]));
}
else
{
p += x[i];
}
var k = BinarySearch.LowerBound(
j => sl.Count - j <= sl[j] + p, 0, sl.Count - 1);
Console.WriteLine(sl.Count - k);
});
}
catch (IndexOutOfRangeException)
{
Environment.Exit(0);
}
}
#region Scanners
static Scanner _scanner;
static char C => _scanner.NextChar();
static string S => _scanner.NextString();
static int I => _scanner.NextInt();
static long L => _scanner.NextLong();
static BigInteger B => _scanner.NextBigInteger();
static double D => _scanner.NextDouble();
static decimal M => _scanner.NextDecimal();
#endregion
public static void Main()
{
var sw = new StreamWriter(Console.OpenStandardOutput());
sw.NewLine = "\n";
#if DEBUG
sw.AutoFlush = true;
#else
sw.AutoFlush = false;
#endif
Console.SetOut(sw);
_scanner = new Scanner(Console.OpenStandardInput());
Solve();
Console.Out.Flush();
}
}
public static partial class Extensions
{
}
// ref. http://kaiseh.com/skiplist/SkipList.java
[DebuggerStepThrough]
class SkipList<T> : IList<T>, IReadOnlyList<T>
{
protected class Pointer<U>
{
public Entry<U> Prev { get; set; }
public Entry<U> Next { get; set; }
public int Distance { get; set; }
public Pointer(Entry<U> prev, Entry<U> next, int distance)
{
this.Prev = prev;
this.Next = next;
this.Distance = distance;
}
}
protected class Entry<U>
{
public Pointer<U>[] Pts { get; set; }
public Entry<U> Prev { get; set; }
public Entry<U> Next { get; set; }
public U Value { get; set; }
public Entry()
{
}
public Entry(int level, Entry<U> prev, Entry<U> next, U value)
{
if (level > 0)
{
this.Pts = new Pointer<U>[level];
}
this.Prev = prev;
this.Next = next;
this.Value = value;
}
public int Level => this.Pts != null ? this.Pts.Length : 0;
}
protected class EntryEnumerator : IEnumerator<T>
{
private SkipList<T> _base;
private Entry<T> _current;
public EntryEnumerator(SkipList<T> @base, Entry<T> current)
{
_base = @base;
_current = current;
}
public T Current => _current.Value;
object IEnumerator.Current => this.Current;
public void Dispose()
{
}
public bool MoveNext()
{
if (_current.Next == _base._head)
{
return false;
}
_current = _current.Next;
return true;
}
public void Reset()
{
throw new NotImplementedException();
}
}
protected Entry<T> _head;
protected int _size;
private int _randomSeed;
public SkipList()
{
var rand = new Random();
_randomSeed = rand.Next() | 0x100;
BuildHead();
}
private void BuildHead()
{
_head = new Entry<T>();
_head.Prev = _head;
_head.Next = _head;
}
private int GenerateRandomLevel()
{
var x = _randomSeed;
x ^= x << 13;
x ^= x >> 17;
_randomSeed = x ^= x << 5;
if ((x & 0x8001) != 0)
{
return 0;
}
var level = 0;
while (((x >>= 1) & 1) != 0)
{
level++;
}
return level;
}
protected Entry<T> AddBefore(T item, Entry<T> entry)
{
var headLevel = _head.Level;
var level = Math.Min(GenerateRandomLevel(), headLevel + 1);
if (level > headLevel)
{
var pts = new Pointer<T>[level];
for (var i = 0; i < headLevel; i++)
{
pts[i] = _head.Pts[i];
}
for (var i = headLevel; i < level; i++)
{
pts[i] = new Pointer<T>(_head, _head, 0);
}
_head.Pts = pts;
headLevel = level;
}
var prev = entry.Prev;
var next = entry;
var e = new Entry<T>(level, prev, next, item);
next.Prev = e;
prev.Next = e;
var prevDistance = 1;
var nextDistance = 1;
for (var i = 0; i < level; i++)
{
while (prev.Pts == null)
{
prevDistance++;
prev = prev.Prev;
}
var lv = prev.Level;
while (lv <= i)
{
var prevPt = prev.Pts[lv - 1];
prevDistance += prevPt.Prev.Pts[lv - 1].Distance;
prev = prevPt.Prev;
lv = prev.Pts.Length;
}
while (next.Pts == null)
{
nextDistance++;
next = next.Next;
}
lv = next.Level;
while (lv <= i)
{
var nextPt = next.Pts[lv - 1];
nextDistance += nextPt.Distance;
next = nextPt.Next;
lv = next.Pts.Length;
}
e.Pts[i] = new Pointer<T>(prev, next, nextDistance);
prev.Pts[i].Next = e;
prev.Pts[i].Distance = prevDistance;
next.Pts[i].Prev = e;
}
for (var i = level; i < headLevel; i++)
{
while (prev.Pts == null)
{
prev = prev.Prev;
}
while (prev.Pts.Length <= i)
{
prev = prev.Pts[prev.Pts.Length - 1].Prev;
}
prev.Pts[i].Distance++;
}
_size++;
return e;
}
protected Entry<T> GetEntry(int index)
{
if (index < 0 || index >= _size)
{
throw new IndexOutOfRangeException($"size: {_size}, index: {index}");
}
var e = _head;
var level = e.Level;
var curIndex = -1;
while (curIndex != index)
{
if (level == 0)
{
e = e.Next;
curIndex++;
}
else
{
var p = e.Pts[level - 1];
var n = curIndex + p.Distance;
if (n <= index)
{
e = p.Next;
curIndex = n;
}
else
{
level--;
}
}
}
return e;
}
protected void RemoveEntry(Entry<T> entry)
{
var prev = entry.Prev;
var next = entry.Next;
prev.Next = next;
next.Prev = prev;
var level = entry.Level;
if (level > 0)
{
for (var i = 0; i < level; i++)
{
var p = entry.Pts[i];
prev = p.Prev;
next = p.Next;
prev.Pts[i].Next = next;
next.Pts[i].Prev = prev;
prev.Pts[i].Distance += p.Distance - 1;
}
prev = entry.Pts[level - 1].Prev;
}
var headLevel = _head.Level;
for (var i = level; i < headLevel; i++)
{
while (prev.Pts == null)
{
prev = prev.Prev;
}
while (i >= prev.Pts.Length)
{
prev = prev.Pts[prev.Pts.Length - 1].Prev;
}
prev.Pts[i].Distance--;
}
_size--;
}
protected int GetIndex(Entry<T> entry)
{
var e = entry;
var distance = 0;
while (e != _head)
{
if (e.Pts == null)
{
distance++;
e = e.Next;
}
else
{
var p = e.Pts[e.Pts.Length - 1];
distance += p.Distance;
e = p.Next;
}
}
return _size - distance;
}
public int Count => _size;
public bool IsReadOnly => throw new NotImplementedException();
public virtual void Clear()
{
BuildHead();
_size = 0;
}
public virtual bool Add(T item)
{
AddBefore(item, _head);
return true;
}
void ICollection<T>.Add(T item) => Add(item);
public virtual void Insert(int index, T item)
{
if (index == _size)
{
AddBefore(item, _head);
}
else
{
var entry = GetEntry(index);
AddBefore(item, entry);
}
}
public virtual void RemoveAt(int index)
{
var entry = GetEntry(index);
RemoveEntry(entry);
}
public virtual T this[int index]
{
get => GetEntry(index).Value;
set
{
var entry = GetEntry(index);
entry.Value = value;
}
}
public virtual int IndexOf(T item)
{
var index = 0;
var e = _head.Next;
if (item == null)
{
for (; e != _head; e = e.Next, index++)
{
if (e.Value == null)
{
return index;
}
}
}
else
{
for (; e != _head; e = e.Next, index++)
{
if (e.Value.Equals(item))
{
return index;
}
}
}
return -1;
}
public IEnumerator<T> GetEnumerator() => new EntryEnumerator(this, _head);
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
bool ICollection<T>.Contains(T item)
{
throw new NotImplementedException();
}
void ICollection<T>.CopyTo(T[] array, int arrayIndex)
{
throw new NotImplementedException();
}
bool ICollection<T>.Remove(T item)
{
throw new NotImplementedException();
}
}
#region Library
public class Scanner
{
private readonly Stream _stream;
private const int _bufferSize = 1024;
private readonly byte[] _buf = new byte[_bufferSize];
private int _len, _ptr;
public Scanner(Stream stream)
{
_stream = stream;
}
public byte ReadByte()
{
if (_ptr >= _len)
{
_len = _stream.Read(_buf, 0, _bufferSize);
_ptr = 0;
}
return _buf[_ptr++];
}
public char ReadChar() => (char)ReadByte();
public string ReadLine()
{
var r = new StringBuilder();
if (_ptr == 0) r.Append(ReadChar());
for (; _ptr < _len; _ptr++) r.Append((char)_buf[_ptr]);
return r.ToString();
}
public char NextChar() => char.Parse(NextString());
public string NextString()
{
var r = new StringBuilder();
var b = ReadChar();
while (b != ' ' && b != '\n')
{
r.Append(b);
b = ReadChar();
}
return r.ToString();
}
public int NextInt() => (int)NextLong();
public long NextLong()
{
var r = 0L;
var b = ReadByte();
var n = b == '-';
if (n) b = ReadByte();
while (b != ' ' && b != '\n')
{
r = r * 10 + b - '0';
b = ReadByte();
}
return n ? -r : r;
}
public BigInteger NextBigInteger()
{
var r = new BigInteger();
var b = ReadByte();
var n = b == '-';
if (n) b = ReadByte();
while (b != ' ' && b != '\n')
{
r = r * 10 + b - '0';
b = ReadByte();
}
return n ? -r : r;
}
public double NextDouble()
{
var i = 0L;
var b = ReadByte();
var n = b == '-';
if (n) b = ReadByte();
while (b != '.' && b != ' ' && b != '\n')
{
i = i * 10 + b - '0';
b = ReadByte();
}
if (b != '.') return n ? -i : i;
b = ReadByte();
var f = 0L;
var p = 0;
while (b != ' ' && b != '\n')
{
f = f * 10 + b - '0';
b = ReadByte();
p++;
}
var r = i + (double)f / MathExtensions.Pow(10, p);
return n ? -r : r;
}
public decimal NextDecimal() => decimal.Parse(NextString());
public T Next<T>(Converter<string, T> parser) => parser(NextString());
}
public static class BinarySearch
{
// source[source.LowerBound(value)] <= value
// Example:
// var source = new[] { 10, 30, 30, 50 };
// source.LowerBound(20) -> 1
// source.LowerBound(30) -> 1
public static int LowerBound<T>(this IReadOnlyList<T> source, T value) where T : IComparable<T>
=> source.LowerBound(value, Comparer<T>.Default);
public static int LowerBound<T>(this IReadOnlyList<T> source, T value, IComparer<T> comparer)
=> LowerBound(i => source[i], 0, source.Count - 1, value, comparer);
public static int LowerBound<T>(
Func<int, T> func, int minValue, int maxValue, T value) where T : IComparable<T>
=> LowerBound(func, minValue, maxValue, value, Comparer<T>.Default);
public static int LowerBound<T>(
Func<int, T> func, int minValue, int maxValue, T value, IComparer<T> comparer)
{
var i = LowerBound(x => comparer.Compare(func(x), value) >= 0, minValue, maxValue);
return i > maxValue ? i : comparer.Compare(func(i), value) < 0 ? i + 1 : i; // hotfix
}
public static int LowerBound(Predicate<int> predicate, int minValue, int maxValue)
=> Search(predicate, maxValue, minValue - 1, out var i) ? i : maxValue + 1;
// value < source[source.UpperBound(value)]
// Example:
// var source = new[] { 10, 30, 30, 50 };
// source.UpperBound(20) -> 1
// source.UpperBound(30) -> 3
// source.UpperBound(50) -> 4
public static int UpperBound<T>(this IReadOnlyList<T> source, T value) where T : IComparable<T>
=> source.UpperBound(value, Comparer<T>.Default);
public static int UpperBound<T>(
Func<int, T> func, int minValue, int maxValue, T value) where T : IComparable<T>
=> UpperBound(func, minValue, maxValue, value, Comparer<T>.Default);
public static int UpperBound<T>(this IReadOnlyList<T> source, T value, IComparer<T> comparer)
=> UpperBound(i => source[i], 0, source.Count - 1, value, comparer);
public static int UpperBound<T>(
Func<int, T> func, int minValue, int maxValue, T value, IComparer<T> comparer)
{
var i = LowerBound(x => comparer.Compare(func(x), value) > 0, minValue, maxValue);
return i > maxValue ? i : comparer.Compare(func(i), value) <= 0 ? i + 1 : i; // hotfix
}
public static int UpperBound(Predicate<int> predicate, int minValue, int maxValue)
=> Search(predicate, minValue, maxValue + 1, out var i) ? i : minValue;
private static bool Search(Predicate<int> predicate, int ok, int ng, out int i)
{
while (Abs(ok - ng) > 1)
{
var mid = ng + (ok - ng) / 2;
if (predicate(mid)) ok = mid;
else ng = mid;
}
if (predicate(ok))
{
i = ok;
return true;
}
else
{
i = default(int);
return false;
}
}
}
public class CoordinateCompressor<T> where T : IComparable<T>, IEquatable<T>
{
private readonly Dictionary<T, int> _compress;
private readonly T[] _decompress;
public CoordinateCompressor(IEnumerable<T> coordinates)
{
var arr = coordinates.ToArray();
Array.Sort(arr);
_compress = new Dictionary<T, int>(arr.Length);
_decompress = arr;
var pi = default(int);
var pa = default(T);
if (arr.Any()) _compress.Add(arr[0], 0); // hotfix
for (var i = 0; i < arr.Length; i++)
if (i > 0 && !arr[i].Equals(pa)) _compress[pa = arr[i]] = pi = i;
}
public int Compress(T coordinate) => _compress[coordinate];
public T Decompress(int index) => _decompress[index];
}
[DebuggerStepThrough]
public static partial class Extensions
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Assert(bool condition)
{
if (!condition) throw new Exception("Assertion failed");
}
public static string AsString(this IEnumerable<char> source) => new string(source.ToArray());
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
{
foreach (var item in source) action(item);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, _> func)
{
foreach (var item in source) func(item);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action)
{
var i = 0;
foreach (var item in source) action(item, i++);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, int, _> func)
{
var i = 0;
foreach (var item in source) func(item, i++);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T Iterate<T>(int count, T seed, Func<T, T> func)
{
var r = seed;
for (var i = 0; i < count; i++) r = func(r);
return r;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Repeat(int count, Action action)
{
for (var i = 0; i < count; i++) action();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Repeat(int count, Action<int> action)
{
for (var i = 0; i < count; i++) action(i);
}
public static IEnumerable<T> Repeat<T>(Func<T> func)
{
for (var i = 0; ; i++) yield return func();
}
public static IEnumerable<T> Repeat<T>(int count, Func<T> func)
{
for (var i = 0; i < count; i++) yield return func();
}
public static IEnumerable<T> Repeat<T>(Func<int, T> func)
{
for (var i = 0; ; i++) yield return func(i);
}
public static IEnumerable<T> Repeat<T>(int count, Func<int, T> func)
{
for (var i = 0; i < count; i++) yield return func(i);
}
public static void Swap<T>(ref T x, ref T y)
{
var tmp = x; x = y; y = tmp;
}
public static (T1[], T2[]) Unzip<T1, T2>(this ICollection<(T1, T2)> source)
{
var ts1 = new T1[source.Count];
var ts2 = new T2[source.Count];
var i = 0;
foreach (var (t1, t2) in source) { ts1[i] = t1; ts2[i] = t2; i++; }
return (ts1, ts2);
}
public static (T1[], T2[], T3[]) Unzip<T1, T2, T3>(this ICollection<(T1, T2, T3)> source)
{
var ts1 = new T1[source.Count];
var ts2 = new T2[source.Count];
var ts3 = new T3[source.Count];
var i = 0;
foreach (var (t1, t2, t3) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; i++; }
return (ts1, ts2, ts3);
}
public static (T1[], T2[], T3[], T4[]) Unzip<T1, T2, T3, T4>(this ICollection<(T1, T2, T3, T4)> source)
{
var ts1 = new T1[source.Count];
var ts2 = new T2[source.Count];
var ts3 = new T3[source.Count];
var ts4 = new T4[source.Count];
var i = 0;
foreach (var (t1, t2, t3, t4) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; ts4[i] = t4; i++; }
return (ts1, ts2, ts3, ts4);
}
public static IEnumerable<T> Zip<T1, T2, T3, T>(this IEnumerable<T1> first, IEnumerable<T2> second, IEnumerable<T3> thrid, Func<T1, T2, T3, T> resultSelector)
{
using (var e1 = first.GetEnumerator())
using (var e2 = second.GetEnumerator())
using (var e3 = thrid.GetEnumerator())
{
while (e1.MoveNext() && e2.MoveNext() && e3.MoveNext())
yield return resultSelector(e1.Current, e2.Current, e3.Current);
}
}
public static IEnumerable<T> Zip<T1, T2, T3, T4, T>(this IEnumerable<T1> first, IEnumerable<T2> second, IEnumerable<T3> thrid, IEnumerable<T4> fourth, Func<T1, T2, T3, T4, T> resultSelector)
{
using (var e1 = first.GetEnumerator())
using (var e2 = second.GetEnumerator())
using (var e3 = thrid.GetEnumerator())
using (var e4 = fourth.GetEnumerator())
{
while (e1.MoveNext() && e2.MoveNext() && e3.MoveNext() && e4.MoveNext())
yield return resultSelector(e1.Current, e2.Current, e3.Current, e4.Current);
}
}
}
[DebuggerStepThrough]
public static class MathExtensions
{
public static int Gcd(int left, int right)
{
int r;
while ((r = left % right) != 0) { left = right; right = r; }
return right;
}
public static long Gcd(long left, long right)
{
long r;
while ((r = left % right) != 0L) { left = right; right = r; }
return right;
}
public static BigInteger Gcd(BigInteger left, BigInteger right)
=> BigInteger.GreatestCommonDivisor(left, right);
public static int HighestOneBit(int x)
{
x |= x >> 01;
x |= x >> 02;
x |= x >> 04;
x |= x >> 08;
x |= x >> 16;
return x - (x >> 1);
}
public static long HighestOneBit(long x)
{
x |= x >> 01;
x |= x >> 02;
x |= x >> 04;
x |= x >> 08;
x |= x >> 16;
x |= x >> 32;
return x - (x >> 1);
}
public static int Lcm(int left, int right) => left / Gcd(left, right) * right;
public static long Lcm(long left, long right) => left / Gcd(left, right) * right;
public static BigInteger Lcm(BigInteger left, BigInteger right)
=> left / Gcd(left, right) * right;
public static int Pow(int value, int exponent)
{
var r = 1;
while (exponent > 0)
{
if ((exponent & 1) == 1) r *= value;
value *= value;
exponent >>= 1;
}
return r;
}
public static long Pow(long value, int exponent)
{
var r = 1L;
while (exponent > 0)
{
if ((exponent & 1) == 1) r *= value;
value *= value;
exponent >>= 1;
}
return r;
}
public static long Fact(int value)
{
var r = 1L;
for (var i = 2; i <= value; i++) r *= i;
return r;
}
}
#endregion