結果

問題 No.953 席
ユーザー aajisakaaajisaka
提出日時 2019-12-16 23:38:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,131 ms / 2,000 ms
コード長 4,749 bytes
コンパイル時間 2,543 ms
コンパイル使用メモリ 191,368 KB
実行使用メモリ 10,044 KB
最終ジャッジ日時 2023-09-15 19:00:26
合計ジャッジ時間 27,704 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1,118 ms
5,140 KB
testcase_03 AC 1,130 ms
5,004 KB
testcase_04 AC 1,126 ms
5,204 KB
testcase_05 AC 1,131 ms
4,752 KB
testcase_06 AC 1,121 ms
5,152 KB
testcase_07 AC 469 ms
9,364 KB
testcase_08 AC 687 ms
8,456 KB
testcase_09 AC 389 ms
10,044 KB
testcase_10 AC 152 ms
5,280 KB
testcase_11 AC 512 ms
7,184 KB
testcase_12 AC 1,011 ms
6,860 KB
testcase_13 AC 833 ms
8,124 KB
testcase_14 AC 1,057 ms
6,652 KB
testcase_15 AC 1,061 ms
6,232 KB
testcase_16 AC 1,076 ms
6,572 KB
testcase_17 AC 949 ms
7,032 KB
testcase_18 AC 987 ms
6,656 KB
testcase_19 AC 856 ms
8,148 KB
testcase_20 AC 979 ms
6,512 KB
testcase_21 AC 1,081 ms
5,160 KB
testcase_22 AC 989 ms
7,364 KB
testcase_23 AC 1,096 ms
5,516 KB
testcase_24 AC 1,092 ms
5,504 KB
testcase_25 AC 741 ms
8,452 KB
testcase_26 AC 1,078 ms
4,740 KB
権限があれば一括ダウンロードができます

ソースコード

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() {
      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
          ll 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
        ll 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;
}
0