結果

問題 No.953 席
ユーザー aajisakaaajisaka
提出日時 2019-12-16 03:06:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,725 bytes
コンパイル時間 2,160 ms
コンパイル使用メモリ 190,060 KB
実行使用メモリ 10,212 KB
最終ジャッジ日時 2024-07-02 19:04:58
合計ジャッジ時間 5,984 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 125 ms
9,696 KB
testcase_08 AC 154 ms
8,732 KB
testcase_09 AC 105 ms
10,212 KB
testcase_10 AC 37 ms
6,940 KB
testcase_11 AC 113 ms
7,296 KB
testcase_12 WA -
testcase_13 AC 152 ms
8,412 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 123 ms
8,488 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 164 ms
8,672 KB
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

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

    int add() {
      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 (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);
      return p;
    }

    void del(int p) {
      assert(p != -1);
      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 != -100) {
        if (st2.find(left[l]) == st2.end() && st1.find(l) != st1.end()) {
          st1.erase(l);
          st0.insert(l);
        }
      }
      if (r != -100) {
        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, -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);
      }
      // 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;
          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;
        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