結果

問題 No.953 席
ユーザー square1001
提出日時 2020-02-06 18:50:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 3,427 bytes
コンパイル時間 1,327 ms
コンパイル使用メモリ 106,996 KB
実行使用メモリ 10,204 KB
最終ジャッジ日時 2024-09-25 06:52:11
合計ジャッジ時間 8,632 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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

#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
class query {
public:
    int tp, id; long long t;
    query() : tp(-1), t(-1), id(-1) {};
    query(int tp_, long long t_, int id_) : tp(tp_), t(t_), id(id_) {};
    bool operator<(const query& q) const {
        return t * 2 - tp > q.t * 2 - q.tp;
    }
};
int main() {
    int N, K1, K2;
    cin >> N >> K1 >> K2; --K1, --K2;
    vector<int> ord(N);
    for (int i = 0; i < N; ++i) {
        int d1 = abs(i - K1), d2 = abs(i - K2);
        if (d1 < d2) {
            ord[i] = 2 * d1;
        }
        else {
            ord[i] = 2 * d2 + 1;
        }
    }
    vector<int> ordsorted = ord;
    sort(ordsorted.begin(), ordsorted.end());
    for (int i = 0; i < N; ++i) {
        ord[i] = lower_bound(ordsorted.begin(), ordsorted.end(), ord[i]) - ordsorted.begin();
    }
    vector<int> ordinv(N);
    for (int i = 0; i < N; ++i) {
        ordinv[ord[i]] = i;
    }
    int Q;
    cin >> Q;
    vector<int> A(Q), B(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> A[i] >> B[i];
    }
    priority_queue<query> que;
    for (int i = 0; i < Q; ++i) {
        que.push(query(0, A[i], i));
    }
    queue<int> que2;
    set<int> sl;
    vector<int> state(N, 0);
    for (int i = 0; i < N; ++i) {
        sl.insert(i);
    }
    vector<int> ans(Q);
    while (!que.empty()) {
        query u = que.top(); que.pop();
        bool repeat = (!que.empty() && u.tp == 1 && u.t == que.top().t);
        if (u.tp == 1) {
            int val = u.id;
            sl.erase(state[val] * N + ord[val]);
            bool pflag = false;
            if (val >= 1 && state[val - 1] == 2) pflag = true;
            if (val <= N - 2 && state[val + 1] == 2) pflag = true;
            state[val] = (pflag ? 1 : 0);
            sl.insert(state[val] * N + ord[val]);
            for (int i = val - 1; i <= val + 1; i += 2) {
                if (!(0 <= i && i < N) || state[i] == 2) continue;
                bool flag = false;
                if (i >= 1 && state[i - 1] == 2) flag = true;
                if (i <= N - 2 && state[i + 1] == 2) flag = true;
                sl.erase(state[i] * N + ord[i]);
                state[i] = (flag ? 1 : 0);
                sl.insert(state[i] * N + ord[i]);
            }
        }
        while (!repeat && !que2.empty()) {
            int id = que2.front();
            int val = *sl.begin();
            if (val >= 2 * N) {
                break;
            }
            else {
                que2.pop();
                val = ordinv[val % N];
                sl.erase(state[val] * N + ord[val]);
                state[val] = 2;
                sl.insert(state[val] * N + ord[val]);
                for (int i = val - 1; i <= val + 1; i += 2) {
                    if (!(0 <= i && i < N) || state[i] == 2) continue;
                    bool flag = false;
                    if (i >= 1 && state[i - 1] == 2) flag = true;
                    if (i <= N - 2 && state[i + 1] == 2) flag = true;
                    sl.erase(state[i] * N + ord[i]);
                    state[i] = (flag ? 1 : 0);
                    sl.insert(state[i] * N + ord[i]);
                }
                que.push(query(1, u.t + B[id], val));
                ans[id] = val;
            }
        }
        if (u.tp == 0) {
            int val = *sl.begin();
            if (val >= 2 * N) {
                que2.push(u.id);
            }
            else {
                val = ordinv[val % N];
                sl.erase(state[val] * N + ord[val]);
                state[val] = 2;
                sl.insert(state[val] * N + ord[val]);
                for (int i = val - 1; i <= val + 1; i += 2) {
                    if (!(0 <= i && i < N) || state[i] == 2) continue;
                    bool flag = false;
                    if (i >= 1 && state[i - 1] == 2) flag = true;
                    if (i <= N - 2 && state[i + 1] == 2) flag = true;
                    sl.erase(state[i] * N + ord[i]);
                    state[i] = (flag ? 1 : 0);
                    sl.insert(state[i] * N + ord[i]);
                }
                ans[u.id] = val;
                que.push(query(1, u.t + B[u.id], val));
            }
        }
    }
    for (int i = 0; i < Q; ++i) {
        cout << ans[i] + 1 << '\n';
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0