結果
| 問題 |
No.3327 うるせぇ、ポリオミノぶつけんぞ
|
| コンテスト | |
| ユーザー |
 鳩でもわかるC#
|
| 提出日時 | 2025-11-01 16:30:53 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 2,197 ms / 3,000 ms |
| コード長 | 8,132 bytes |
| コンパイル時間 | 8,965 ms |
| コンパイル使用メモリ | 170,868 KB |
| 実行使用メモリ | 237,640 KB |
| 最終ジャッジ日時 | 2025-11-01 16:31:41 |
| 合計ジャッジ時間 | 44,826 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (117 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using AtCoder;
using AtCoder.Internal;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.Intrinsics.X86;
class Program
{
static string ReadLine() => Console.ReadLine().Trim();
static int ReadInt() => int.Parse(ReadLine());
static long ReadLong() => long.Parse(ReadLine());
static int[] ReadIntArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => int.Parse(_)).ToArray() : new int[0]; }
static long[] ReadLongArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => long.Parse(_)).ToArray() : new long[0]; }
static (int a, int b) ReadInt2() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1]); }
static (int a, int b, int c) ReadInt3() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1], c: vs[2]); }
static (int a, int b, int c, int d) ReadInt4() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1], c: vs[2], d: vs[3]); }
static (long a, long b) ReadLong2() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1]); }
static (long a, long b, long c) ReadLong3() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1], c: vs[2]); }
static (long a, long b, long c, long d) ReadLong4() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1], c: vs[2], d: vs[3]); }
class Node
{
public Node(int idx, int val)
{
Index = idx;
Value = val;
}
public Node()
{
Index = -1;
Value = int.MinValue;
}
public int Index = 0;
public int Value = 0;
}
struct OP2 : ISegtreeOperator<Node>
{
Node ISegtreeOperator<Node>.Identity => new Node();
Node ISegtreeOperator<Node>.Operate(Node x, Node y)
{
if (x.Value > y.Value)
return x;
else
return y;
}
}
struct OP : ISegtreeOperator<int>
{
int ISegtreeOperator<int>.Identity => int.MinValue;
int ISegtreeOperator<int>.Operate(int x, int y)
{
if (x > y)
return x;
else
return y;
}
}
static void Main()
{
SourceExpander.Expander.Expand();
(int N, int Q) = ReadInt2();
int[] A = ReadIntArray();
Node[] nodes = new Node[N];
for (int i = 0; i < N; i++)
nodes[i] = new Node(i, A[i]);
Segtree<int, OP> seg = new Segtree<int, OP>(A);
for (int i = 0; i < Q; i++)
{
(int t, int x) = ReadInt2();
if (t == 1)
{
int ok = N;
int ng = -1;
int idx = StlFunction.BinarySearch(ok, ng, mid => {
return seg.Prod(0, mid + 1) > x;
});
if (idx < N)
{
Console.WriteLine(idx + 1);
seg[idx] = int.MinValue;
}
else
Console.WriteLine(-1);
}
if (t == 2)
{
int ok = -1;
int ng = N;
int idx = StlFunction.BinarySearch(ok, ng, mid => {
return seg.Prod(mid, N) > x;
});
if (idx > -1)
{
Console.WriteLine(idx + 1);
seg[idx] = int.MinValue;
}
else
Console.WriteLine(-1);
}
}
}
}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace AtCoder{public interface ISegtreeOperator<T>{T Identity{get;}T Operate(T x,T y);}}
namespace AtCoder{public class Segtree<TValue,TOp>where TOp:struct,ISegtreeOperator<TValue>{private static readonly TOp op=default;public int Length{get;}internal readonly int log;internal readonly int size;public readonly TValue[]d;public Segtree(int n){Length=n;log=InternalBit.CeilPow2(n);size=1<<log;d=new TValue[2*size];Array.Fill(d,op.Identity);}public Segtree(TValue[]v):this((ReadOnlySpan<TValue>)v){}public Segtree(Span<TValue>v):this((ReadOnlySpan<TValue>)v){}public Segtree(ReadOnlySpan<TValue>v):this(v.Length){v.CopyTo(d.AsSpan(size));for(int i=size-1;i>=1;i--){Update(i);}}[MethodImpl(256)]public void Update(int k)=>d[k]=op.Operate(d[2*k],d[2*k+1]);public TValue this[int p]{[MethodImpl(256)]set{p+=size;d[p]=value;for(int i=1;i<=log;i++)Update(p>>i);}[MethodImpl(256)]get{return d[p+size];}}[MethodImpl(256)]public TValue Slice(int l,int len)=>Prod(l,l+len);[MethodImpl(256)]public TValue Prod(int l,int r){TValue sml=op.Identity,smr=op.Identity;l+=size;r+=size;while(l<r){if((l&1)!=0)sml=op.Operate(sml,d[l++]);if((r&1)!=0)smr=op.Operate(d[ --r],smr);l>>=1;r>>=1;}return op.Operate(sml,smr);}public TValue AllProd=>d[1];[MethodImpl(256)]public int MaxRight(int l,Predicate<TValue>f){if(l==Length)return Length;l+=size;var sm=op.Identity;do{while(l%2==0)l>>=1;if(!f(op.Operate(sm,d[l]))){while(l<size){l=(2*l);if(f(op.Operate(sm,d[l]))){sm=op.Operate(sm,d[l]);l++;}}return l-size;}sm=op.Operate(sm,d[l]);l++;}while((l&-l)!=l);return Length;}[MethodImpl(256)]public int MinLeft(int r,Predicate<TValue>f){if(r==0)return 0;r+=size;var sm=op.Identity;do{r--;while(r>1&&(r%2)!=0)r>>=1;if(!f(op.Operate(d[r],sm))){while(r<size){r=(2*r+1);if(f(op.Operate(d[r],sm))){sm=op.Operate(d[r],sm);r--;}}return r+1-size;}sm=op.Operate(d[r],sm);}while((r&-r)!=r);return 0;}}}
namespace AtCoder.Internal{public static class InternalBit{[MethodImpl(256)]public static uint ExtractLowestSetBit(int n){if(Bmi1.IsSupported){return Bmi1.ExtractLowestSetBit((uint)n);}return(uint)(n&-n);}[MethodImpl(256)]public static int Bsf(uint n){return BitOperations.TrailingZeroCount(n);}[MethodImpl(256)]public static int CeilPow2(int n){var un=(uint)n;if(un<=1)return 0;return BitOperations.Log2(un-1)+1;}}}
namespace AtCoder{public static class StlFunction{public struct NextPermutationEnumerator<T>:IEnumerator<T[]>,IEnumerable<T[]>where T:IComparable<T>{internal readonly IEnumerable<T>_orig;internal NextPermutationEnumerator(IEnumerable<T>orig){_orig=orig;Current=null;}public T[]Current{get;private set;}[MethodImpl(256)]public bool MoveNext(){if(Current==null){Current=_orig.ToArray();return true;}return NextPermutation(Current);}public void Reset()=>Current=null;object IEnumerator.Current=>Current;void IDisposable.Dispose(){}[MethodImpl(256)]public NextPermutationEnumerator<T>GetEnumerator()=>this;IEnumerator<T[]>IEnumerable<T[]>.GetEnumerator()=>this;IEnumerator IEnumerable.GetEnumerator()=>this;}[MethodImpl(256)]public static bool NextPermutation<T>(T[]array)where T:IComparable<T> =>NextPermutation(array.AsSpan());[MethodImpl(256)]public static bool NextPermutation<T>(Span<T>span)where T:IComparable<T>{int i;for(i=span.Length-2;i>=0;i--)if(span[i].CompareTo(span[i+1])<0)break;if(i<0)return false;int j;for(j=span.Length-1;j>=0;j--)if(span[i].CompareTo(span[j])<0)break;(span[i],span[j])=(span[j],span[i]);span.Slice(i+1,span.Length-i-1).Reverse();return true;}[MethodImpl(256)]public static NextPermutationEnumerator<T>Permutations<T>(IEnumerable<T>orig)where T:IComparable<T> =>new NextPermutationEnumerator<T>(orig);private struct DefaultComparer<T>:IComparer<T>where T:IComparable<T>{[MethodImpl(256)]public int Compare(T x,T y)=>x.CompareTo(y);}[MethodImpl(256)]public static int BinarySearch(int ok,int ng,Predicate<int>Ok){while(Math.Abs(ok-ng)>1){var m=(ok+ng)>>1;if(Ok(m))ok=m;else ng=m;}return ok;}[MethodImpl(256)]public static long BinarySearch(long ok,long ng,Predicate<long>Ok){while(Math.Abs(ok-ng)>1){var m=(ok+ng)>>1;if(Ok(m))ok=m;else ng=m;}return ok;}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander