結果

問題 No.953 席
コンテスト
ユーザー bal4u
提出日時 2020-01-13 22:23:27
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 4,226 bytes
コンパイル時間 739 ms
コンパイル使用メモリ 33,024 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 02:20:15
合計ジャッジ時間 6,037 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yuki 953 席
// 2019.1.13 bal4u

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

typedef long long ll;

#if 1
int getchar_unlocked(void);
int putchar_unlocked(int c);
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

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

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

#define MAX 100010

// n:入口からの順番, f:客が座っている, pos:優先度キューでの位置
typedef struct { int n; char f; int pos; } T;
T seat[MAX];
int N, K1, K2;

typedef struct { ll a; int n; } QUM;
QUM qum[MAX]; int qsizm;
typedef struct { int n; char lr; int idx; } QUS;
QUS qus[MAX]; int qsizs; 

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

int pqcmp(QUS *u, QUS *v);

void m_min_heapify(int i) {
	int l, r, mi;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsizm && qum[l].a < qum[i].a) mi = l; else mi = i;
	if (r < qsizm && qum[r].a < qum[mi].a) mi = r;
	if (mi != i) {
		QUM qt = qum[i]; qum[i] = qum[mi]; qum[mi] = qt;
		m_min_heapify(mi);
	}
}

void m_deq() {
	qum[0] = qum[--qsizm];
	m_min_heapify(0);
}

void m_enq(ll a, int n) {
	int i, mi;

	i = qsizm++;
	qum[i].a = a, qum[i].n = n;
	while (i > 0 && qum[i].a < qum[mi = PARENT(i)].a) {
		QUM qt = qum[i]; qum[i] = qum[mi]; qum[mi] = qt;
		i = mi;
	}
}

#define idx_update(p, v) (seat[(p)].pos = (v))

void s_min_heapify(int i) {
	int l, r, mi;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsizs && pqcmp(qus+l, qus+i) < 0) mi = l; else mi = i;
	if (r < qsizs && pqcmp(qus+r, qus+mi) < 0) mi = r;
	if (mi != i) {
		idx_update(qus[i].idx, mi);
		idx_update(qus[mi].idx, i);
		QUS qt = qus[i]; qus[i] = qus[mi]; qus[mi] = qt;
		s_min_heapify(mi);
	}
}

void s_deq() {
	qus[0] = qus[--qsizs];
	idx_update(qus[qsizs].idx, 0);
	s_min_heapify(0);
}

void s_enq(int n, char lr) {
	int i, mi;

	i = qsizs++;
	qus[i].n = n, qus[i].idx = n, qus[i].lr = lr;
	idx_update(n, i);
	while (i > 0 && pqcmp(qus+i, qus+(mi = PARENT(i))) < 0) {
		idx_update(qus[i].idx, mi);
		idx_update(qus[mi].idx, i);
		QUS qt = qus[i]; qus[i] = qus[mi]; qus[mi] = qt;
		i = mi;
	}
}

void s_update(int n) { // iは変更対象となるデータの位置、lrは変更後の内容
	int i = seat[n].pos;
	int lr = 0;
	if (n > 1) lr |= seat[n-1].f;
	if (n < N) lr |= seat[n+1].f;
	if (qus[i].lr == lr) return;
#if 0
if (qus[i].n != n) {
	printf("Panic n=%d, pq=%d\n", n, qus[i].n);
	exit(1);
}
#endif
	QUS old = qus[i];    // 変更前の内容
	qus[i].lr = lr;      // 変更後の内容
	if (pqcmp(&old, qus+i) < 0) // 優先度の低いほうへの変更
    	s_min_heapify(i);
  	else {  // 優先度の高いほうへの変更
    	int mi; QUS t;
    	while (i > 0 &&
      	pqcmp(qus+i, qus+(mi=PARENT(i))) < 0) {
      		idx_update(qus[i].idx, mi);
      		idx_update(qus[mi].idx, i);
      		t = qus[i], qus[i] = qus[mi], qus[mi] = t;
      		i = mi;
    	}
  	}
}

int pqcmp(QUS *u, QUS *v) {
	int t = u->lr - v->lr;
	if (t) return t;
	return seat[u->n].n - seat[v->n].n;
}

int main()
{
	N = in(), K1 = in(), K2 = in();
	
	int n = 0;
	seat[K1].n = ++n, seat[K2].n = ++n;
	int i, j = 2; for (i = 1; j < N; ++i) {
		if (K2 < K1) {
			if (K1+i <= N) seat[K1+i].n = ++n, ++j;
			if (K2-i >= 1) seat[K2-i].n = ++n, ++j;
		} else {
			if (K1-i >= 1) seat[K1-i].n = ++n, ++j;
			if (K2+i <= N) seat[K2+i].n = ++n, ++j;
		}
	}
	for (i = 1; i <= N; ++i) s_enq(seat[i].n, 0);
	
	int Q = in();
	ll pre = -1;
	while (Q--) {
		ll a = in(); int b = in();
		if (a < pre) a = pre;
		if (qsizs == 0 && a < qum[0].a) a = qum[0].a;
		while (qsizm > 0 && qum[0].a <= a) {
			n = qum[0].n, m_deq();
			seat[n].f = 0;
			if (n > 1 && seat[n-1].f == 0) s_update(n-1);
			if (n < N && seat[n+1].f == 0) s_update(n+1);
			s_enq(n, seat[n-1].f | seat[n+1].f);
		}
		n = qus[0].n, s_deq();
		seat[n].f = 1, m_enq(a+b, n);
		if (n > 1 && seat[n-1].f == 0) s_update(n-1);
		if (n < N && seat[n+1].f == 0) s_update(n+1);
		out(n);
		pre = a;
	}
	return 0;
}
0