結果
問題 | No.953 席 |
ユーザー | aajisaka |
提出日時 | 2019-12-16 23:33:19 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 4,818 bytes |
コンパイル時間 | 4,949 ms |
コンパイル使用メモリ | 192,352 KB |
実行使用メモリ | 9,988 KB |
最終ジャッジ日時 | 2023-09-15 18:57:58 |
合計ジャッジ時間 | 6,458 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 52 ms
4,904 KB |
testcase_03 | AC | 48 ms
4,616 KB |
testcase_04 | AC | 51 ms
4,892 KB |
testcase_05 | AC | 44 ms
4,596 KB |
testcase_06 | AC | 52 ms
4,820 KB |
testcase_07 | AC | 88 ms
9,368 KB |
testcase_08 | AC | 99 ms
8,364 KB |
testcase_09 | AC | 78 ms
9,988 KB |
testcase_10 | AC | 27 ms
5,384 KB |
testcase_11 | AC | 73 ms
7,168 KB |
testcase_12 | AC | 80 ms
6,888 KB |
testcase_13 | AC | 97 ms
8,044 KB |
testcase_14 | AC | 72 ms
6,412 KB |
testcase_15 | AC | 68 ms
6,052 KB |
testcase_16 | AC | 71 ms
6,400 KB |
testcase_17 | AC | 77 ms
6,752 KB |
testcase_18 | AC | 71 ms
6,420 KB |
testcase_19 | AC | 94 ms
8,312 KB |
testcase_20 | AC | 71 ms
6,492 KB |
testcase_21 | AC | 55 ms
5,272 KB |
testcase_22 | AC | 83 ms
7,296 KB |
testcase_23 | AC | 59 ms
5,756 KB |
testcase_24 | AC | 60 ms
5,632 KB |
testcase_25 | AC | 103 ms
8,092 KB |
testcase_26 | AC | 37 ms
4,604 KB |
ソースコード
/** * 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; }