結果

問題 No.649 ここでちょっとQK!
ユーザー nanaenanae
提出日時 2018-02-09 23:48:29
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 297 ms / 3,000 ms
コード長 2,317 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 113,076 KB
実行使用メモリ 25,784 KB
最終ジャッジ日時 2024-06-12 23:49:52
合計ジャッジ時間 6,663 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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

import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;
void main() {
import std.typecons : Tuple;
alias Query = Tuple!(int, "type", long, "value");
int q, k;
scan(q, k);
auto qs = new Query[](q);
auto a = new long[](0);
foreach (i ; 0 .. q) {
auto line = readln.split.to!(long[]);
if (line.length == 1) {
qs[i] = Query(2, -1);
}
else {
qs[i] = Query(1, line[1]);
a ~= line[1];
}
}
a = a.sort().uniq.array;
int[long] map;
foreach (i, ai; a) {
map[ai] = i.to!int;
}
auto ft = FenwickTree!(int)(q);
foreach (i ; 0 .. q) {
if (qs[i].type == 2) {
if (ft.sum(q) < k) {
writeln(-1);
}
else {
int btm = 0, top = q;
while (top - btm > 1) {
int mid = (top + btm) / 2;
if (ft.sum(mid) >= k) {
top = mid;
}
else {
btm = mid;
}
}
writeln(a[top-1]);
ft.add(top-1, -1);
}
}
else {
ft.add(map[qs[i].value], 1);
}
}
}
struct FenwickTree(T) {
private {
int size;
T[] data;
}
this (int N) {
size = N + 1;
data = new T[](size);
}
void add(int i, int x) {
i++;
while (i < size) {
data[i] += x;
i += i & (-i);
}
}
T sum(int r) {
T res = 0;
while (r > 0) {
res += data[r];
r -= r & (-r);
}
return res;
}
}
void scan(T...)(ref T args) {
import std.stdio : readln;
import std.algorithm : splitter;
import std.conv : to;
import std.range.primitives;
auto line = readln().splitter();
foreach (ref arg; args) {
arg = line.front.to!(typeof(arg));
line.popFront();
}
assert(line.empty);
}
void fillAll(R, T)(ref R arr, T value) {
static if (is(typeof(arr[] = value))) {
arr[] = value;
}
else {
foreach (ref e; arr) {
fillAll(e, value);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0