結果
問題 |
No.618 labo-index
|
ユーザー |
![]() |
提出日時 | 2017-12-18 01:23:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 6,000 ms |
コード長 | 1,735 bytes |
コンパイル時間 | 946 ms |
コンパイル使用メモリ | 84,404 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-15 23:36:42 |
合計ジャッジ時間 | 3,349 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; struct BIT { BIT(int n) : s(n + 1), n(n) {} int sum(int k) { int r = 0; for (; k > 0; k -= k & -k) r += s[k]; return r; } void add(int i, int v) { for (int k = i + 1; k <= n; k += k & -k) s[k] += v; } vector<int> s; int n; }; using I = int; template <class F> I lower_bound(I i0, I i1, F f) { while (i0 < i1) { I i = (i0 + i1) / 2; if (f(i)) i1 = i; else i0 = i + 1; } return i0; } int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; vector<int> t(q), x(q); for (int i = 0; i < q; i++) { cin >> t[i] >> x[i]; if (t[i] == 2) x[i]--; } vector<pair<int64_t, int>> a; int64_t d = 0; for (int i = 0; i < q; i++) { if (t[i] == 1) a.push_back(pair<int64_t, int>(x[i] - d, i)); if (t[i] == 3) d += x[i]; } int n = a.size(); vector<int> p2(n, -1); for (int j = 0; j < n; j++) { p2[j] = a[j].second; } sort(a.begin(), a.end()); vector<int> p(q, -1); for (int j = 0; j < n; j++) { p[a[j].second] = j; } BIT bt(n); d = 0; int m = 0; for (int i = 0; i < q; i++) { if (t[i] == 1) { bt.add(p[i], 1); m++; } else if (t[i] == 2) { bt.add(p[p2[x[i]]], -1); m--; } else { d += x[i]; } I j = lower_bound(0, n, [&](I j) { return m - bt.sum(j) <= a[j].first + d; }); cout << m - bt.sum(j) << '\n'; } return 0; }