結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0