#409056 (C++14) No.953 席

• 問題: No.953 席
• ユーザー: aajisaka
• 提出日時: 2019-12-16 02:38:38
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 4,749 bytes
• コンパイル時間: 2,355 ms
• コンパイル使用メモリ: 193,432 KB
• 実行使用メモリ: 10,084 KB
• 最終ジャッジ日時: 2024-07-02 19:02:41
• 合計ジャッジ時間: 27,093 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 8 WA * 17

ソースコード

/**
 * 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, st2;

    int add() {
      cerr << "add" << endl;
      int p;
      if (!st0.empty()) {
        p = *(st0.begin());
        st0.erase(p);
        st2.insert(p);
      } else if (!st1.empty()) {
        p = *(st1.begin());
        st1.erase(p);
        st2.insert(p);
      } else {
        return -1;
      }
      int l = left[p];
      int r = right[p];
      if (st0.find(l) != st0.end()) {
        st0.erase(l);
        st1.insert(l);
      }
      if (st0.find(r) != st0.end()) {
        st0.erase(r);
        st1.insert(r);
      }
      debug(p);
      return p;
    }

    void del(int p) {
      cerr << "del" << endl;
      st2.erase(p);
      int l = left[p];
      int r = right[p];
      if (st2.find(l) == st2.end() && st2.find(r) == st2.end()) {
        st0.insert(p);
      } else {
        st1.insert(p);
      }

      if (l != -1) {
        if (st2.find(left[l]) == st2.end() && st1.find(l) != st1.end()) {
          st1.erase(l);
          st0.insert(l);
        }
      }
      if (r != -1) {
        if (st2.find(right[r]) == st2.end() && st1.find(r) != st1.end()) {
          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);
      }
      // rev[k1] -> 0;
      rev.resize(n+1);
      rep(i, n) {
        rev[a[i]] = i;
      }
      left.resize(n, -1);
      right.resize(n, -1);
      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);
      }
      // 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
          int t = que.top().first;
          debug(t);
          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
        int t = que.top().first;
        debug(t);
        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;
}