結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー bal4u
提出日時 2019-06-02 09:56:28
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 67 ms / 3,000 ms
コード長 2,136 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-17 20:06:08
合計ジャッジ時間 2,511 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:17:17: note: in expansion of macro 'gc'
   17 |         int c = gc();
      |                 ^~
main.c: In function 'out':
main.c:9:15: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
    9 | #define pc(c) putchar_unlocked(c)
      |               ^~~~~~~~~~~~~~~~
main.c:27:17: note: in expansion of macro 'pc'
   27 |         if (!n) pc('0');
      |                 ^~

ソースコード

diff # 

// yukicoder: 649 ここでちょっとQK
// 2019.6.2 bal4u

#include <stdio.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
long long in()    // 非負整数の入力
{
	long long n = 0;
	int c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

void out(long long n)  // 非負整数の表示（出力）
{
	int i;
	char b[40];

	if (!n) pc('0');
	else {
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}

#define MAXVAL 200000
int bit[MAXVAL+5];
int sz = MAXVAL;
int p = 1<<18;
#if 0
void init(int maxVal) {
	sz = maxVal;
	p = 1; while (p < sz) p <<= 1;
}
#endif

void add(int i, int x) {
	i++; while (i <= sz)
		bit[i] += x, i += i & -i;
}

void insert(int val) { add(val, 1); }
void erase(int val) { add(val, -1); }

int nth_element(int n) {
	int a = 0, q = p; n--;
	while (q >>= 1)
		if (a+q <= sz && bit[a+q] <= n)
			a += q, n -= bit[a];
	return a;
}

int cmp(const void *a, const void *b) {
	long long t;
	t = *(long long *)a - *(long long *)b;
	if (t < 0) return -1;
	return t > 0;
}

// 配列 a 、個数 n　、　リターン値はユニーク化した配列の長さ（個数）
int uniq(long long *a, int n) {
	int i = 0, j;
	a[n] = a[n-1] + 1;
	for (j = 1; j < n; j++) {
		while (a[j] == a[i]) j++;
		a[++i] = a[j];
	}
	if (a[i] < a[n]) i++;
	return i;
}

int Q, K;
int q[MAXVAL]; long long v[MAXVAL];
long long u[MAXVAL]; int sz;

int bsch(long long x)
{
	int m, l = 0, r = sz-1;

    while (l < r) {
        m = (l + r) >> 1;
		if (u[m] == x) return m;
        if (u[m] < x) l = m + 1; else r = m;
    }
	return l;
}

int main()
{
	int i, a, ans, f;
	
	Q = (int)in(), K = (int)in();
	sz = 0; for (i = 0; i < Q; i++) {
		q[i] = (gc() & 1) - 1, gc();
		if (!q[i]) v[i] = in(), u[sz++] = v[i];
	}
	qsort(u, sz, sizeof(long long), cmp);
	sz = uniq(u, sz);
	f = 0; for (i = 0; i < Q; i++) {
		if (q[i]) {
			if (f < K) pc('-'), pc('1'), pc('\n');
			else out(u[a = nth_element(K)]), erase(a), f--;
		} else insert(bsch(v[i])), f++;
	}
	return 0;
}
0