結果

問題 No.953 席
ユーザー aajisaka
提出日時 2019-12-16 23:33:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 4,818 bytes
コンパイル時間 2,304 ms
コンパイル使用メモリ 195,224 KB
実行使用メモリ 10,212 KB
最終ジャッジ日時 2024-07-02 20:53:50
合計ジャッジ時間 5,368 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

constexpr double PI = 3.14159265358979323846;
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

class Seki {

    int n;
    vector<int> a;
    vector<int> rev;
    vector<int> left;
    vector<int> right;

    // st0: non-used
    // st1: left or right used
    // st2: used
    set<int> st0, st1;
    vector<bool> v2;

    int add() {
      int p;
      if (!st0.empty()) {
        p = *(st0.begin());
        st0.erase(p);
        v2[p] = true;
      } else if (!st1.empty()) {
        p = *(st1.begin());
        st1.erase(p);
        v2[p] = true;
      } else {
        return -1;
      }
      int l = left[p];
      int r = right[p];
      if (l != -100 && st0.find(l) != st0.end()) {
        st0.erase(l);
        st1.insert(l);
      }
      if (r != -100 && st0.find(r) != st0.end()) {
        st0.erase(r);
        st1.insert(r);
      }
      assert(0 <= p && p < n);
      //cerr << "add " << p << endl;
      return p;
    }

    void del(const int p) {
      debug(p);
      assert(v2[p]);
      v2[p] = false;
      int l = left[p];
      int r = right[p];
      if ((l < 0 || !v2[l]) && (r < 0 || !v2[r])) {
        st0.insert(p);
      } else {
        st1.insert(p);
      }

      if (l >= 0) {
        int l2 = left[l];
        if (!v2[l] && (l2 < 0 || !v2[l2])) {
          st1.erase(l);
          st0.insert(l);
        }
      }
      if (r >= 0) {
        int r2 = right[r];
        if (!v2[r] && (r2 < 0 || !v2[r2])) {
          st1.erase(r);
          st0.insert(r);
        }
      }
    }

public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int k1, k2; cin >> n >> k1 >> k2;
      // a[0] -> k1;
      a.push_back(k1);
      a.push_back(k2);
      for(int i=1; i<=n; i++) {
        int p = k1+(k1-k2)*i;
        if (1<=p && p<=n) a.push_back(p);
        int q = k2+(k2-k1)*i;
        if (1<=q && q<=n) a.push_back(q);
      }
      assert(a.size() == n);
      // rev[k1] -> 0;
      rev.resize(n+1);
      rep(i, n) {
        rev[a[i]] = i;
      }
      left.resize(n, -100);
      right.resize(n, -100);
      for(int i=1; i<n; i++) {
        int l = rev[i];
        int r = rev[i+1];
        left[r] = l;
        right[l] = r;
      }

      rep(i, n) {
        st0.insert(i);
      }
      v2.resize(n);
      // P(when to leave, where)
      priority_queue<P, vector<P>, greater<>> que;
      // waitlist (who 0-indexed)
      deque<int> deq;

      int q; cin >> q;
      vector<int> x(q), y(q);
      rep(i, q) {
        cin >> x[i] >> y[i];
      }
      vector<int> ans(q);

      rep(i, q) {
        // do before x[i];
        while(!que.empty() && que.top().first <= x[i]) {
          // remove
          ll t = que.top().first;
          while(!que.empty() && que.top().first == t) {
            auto pa = que.top(); que.pop();
            del(pa.second);
          }

          while(!deq.empty()) {
            int w = deq.front();
            int ret = add();
            if (ret == -1) break;
            deq.pop_front();
            ans[w] = ret;
            que.emplace(t+y[w], ret);
          }
        }
        // do x[i];
        int ret = add();
        if (ret == -1) {
          // move to waitlist
          deq.push_back(i);
        } else {
          ans[i] = ret;
          que.emplace(x[i]+y[i], ret);
        }
      }

      while(!que.empty()) {
        // remove
        ll t = que.top().first;
        while(!que.empty() && que.top().first == t) {
          auto pa = que.top(); que.pop();
          del(pa.second);
        }

        while(!deq.empty()) {
          int w = deq.front();
          int ret = add();
          if (ret == -1) break;
          deq.pop_front();
          ans[w] = ret;
          que.emplace(t+y[w], ret);
        }
      }


      rep(i, q) {
        cout << a[ans[i]] << '\n';
      }
    }
};

signed main() {
  Seki solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}
0