結果

問題 No.875 Range Mindex Query
ユーザー iwkjoseciwkjosec
提出日時 2019-10-05 20:26:18
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 116 ms / 2,000 ms
コード長 3,647 bytes
コンパイル時間 2,637 ms
コンパイル使用メモリ 117,160 KB
実行使用メモリ 27,032 KB
最終ジャッジ日時 2024-10-06 23:50:19
合計ジャッジ時間 3,828 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
23,356 KB
testcase_01 AC 22 ms
23,352 KB
testcase_02 AC 22 ms
23,480 KB
testcase_03 AC 22 ms
25,332 KB
testcase_04 AC 23 ms
23,224 KB
testcase_05 AC 23 ms
23,444 KB
testcase_06 AC 24 ms
23,604 KB
testcase_07 AC 24 ms
25,520 KB
testcase_08 AC 24 ms
23,424 KB
testcase_09 AC 22 ms
23,480 KB
testcase_10 AC 23 ms
25,488 KB
testcase_11 AC 116 ms
26,628 KB
testcase_12 AC 99 ms
26,056 KB
testcase_13 AC 87 ms
26,728 KB
testcase_14 AC 83 ms
26,800 KB
testcase_15 AC 110 ms
25,016 KB
testcase_16 AC 109 ms
26,928 KB
testcase_17 AC 113 ms
27,032 KB
testcase_18 AC 113 ms
27,020 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
class Program
{
static void Main()
{
SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false });
var N = S.Int();
var Q = S.Int();
var a=new Pair[N];
for (int i = 0; i < a.Length; i++)
{
a[i]=new Pair(i+1,S.Int());
}
var s = new SegmentTree<Pair>(a, Mindex, new Pair(0, int.MaxValue));
for (int i = 0; i < Q; i++)
{
var q = S.Int();
var l = S.Int() - 1;
var r = S.Int() + (q == 1 ? -1 : 0);
if (q == 1)
{
var k = s[l].Value;
s[l] = new Pair(l + 1, s[r].Value);
s[r] = new Pair(r + 1, k);
}
else
{
WriteLine(s.Query(l, r).Key);
}
}
Out.Flush();
}
static Pair Mindex(Pair l, Pair r) => l.Value < r.Value ? l : r;
}
public class SegmentTree<T>
{
T[] buffer;//0-index
int N;
public int Length => N;
T TI;
Func<T, T, T> F;// 
public SegmentTree(int length, Func<T, T, T> f, T ti)// C#9.0
{
N = length;
buffer = new T[N * 2 - 1];
for (int i = 0; i < buffer.Length; i++) buffer[i] = ti; //!
F = f;
TI = ti;
}
public SegmentTree(T[] init, Func<T, T, T> f, T ti)
{
N = init.Length;
buffer = new T[N * 2 - 1];
Array.Copy(init, 0, buffer, N - 1, init.Length);
for (int i = N - 2; i >= 0; i--)
{
buffer[i] = f(buffer[i * 2 + 1], buffer[i * 2 + 2]);
}
F = f;
TI = ti;
}
public void Update(int k, T v)//k [0, N)
{
k += N - 1;
buffer[k] = v;
while (k > 0)
{
k = (k - 1) >> 1;
buffer[k] = F(buffer[k * 2 + 1], buffer[k * 2 + 2]);
}
}
public T this[int k]
{
set//setC#7.0
{
Update(k, value);
}
get
{
return buffer[k + N - 1];
}
}
public T Query(int l, int r)//[l, r) 0 <= l, r <= N // 0 <= r - l
{
var lv = TI;
var rv = TI;
l += N - 1;
r += N - 1;
while (l < r)
{
if ((l & 1) == 0)
{
lv = F(lv, buffer[l]);
}
if ((r & 1) == 0)
{
rv = F(buffer[r - 1], rv);
}
l >>= 1;
r = (r - 1) >> 1;
}
return F(lv, rv);
}
}
public static class S
{
static System.IO.Stream str = System.Console.OpenStandardInput();
const int size = 10024;
static byte[] buffer = new byte[size];
static int ptr = size;
static bool isEof;
static byte Read()
{
if (ptr == size)
{
isEof = str.Read(buffer, 0, size) == 0;
ptr = 0;
}
return buffer[ptr++];
}
public static int Int()
{
var c = Read();
while (c < 0x21)
{
c = Read();
}
var n = false;
if (c == '-')
{
n = true;
c = Read();
}
var ret = 0;
while (c > 0x20)
{
ret = ret * 10 + c - '0';
c = Read();
}
return n ? -ret : ret;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0