結果

問題 No.953 席
コンテスト
ユーザー bal4u
提出日時 2020-01-14 07:44:37
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 5,024 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-24 06:13:35
合計ジャッジ時間 3,957 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 seat0[MAX], *seat = seat0 + 1;  // seat0:配列のインデックス-1を使いたいため
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)

// m_ 客管理用
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;
	}
}

// s_ 席管理用 優先度が変更可能な優先度付きキュー!!!!!!!!
#define idx_update(p, v) (seat[(p)].pos = (v))
static inline int pqcmp(QUS *u, QUS *v) {
	int t;
	if (t = u->lr - v->lr) return t;
	return seat[u->n].n - seat[v->n].n;
}

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は変更対象となるデータの位置
	int i = seat[n].pos;
	int lr = seat[n-1].f | seat[n+1].f; // lr:変更後の内容
	
	if (qus[i].lr == lr) return; // 優先度変更なし

	QUS old = qus[i];    // 変更前の内容
	qus[i].lr = lr;      // 変更後の内容
	if (pqcmp(&old, qus+i) < 0) // 優先度の低いほうへの変更
    	s_min_heapify(i);
  	else {                      // 優先度の高いほうへの変更
    	int mi;
    	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;
    	}
  	}
}

// メイン関数
int main()
{
	N = in(), K1 = in(), K2 = in();
	
	// 入口に近い席を優先（昇順）する。 n:1,2,3,...,N
	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);
	
	// リクエスト処理
	ll pre = -1;  // 前の客の入席時刻
	int Q = in();
	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