結果
問題 | No.618 labo-index |
ユーザー | Pachicobue |
提出日時 | 2017-12-22 02:34:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,399 bytes |
コンパイル時間 | 2,910 ms |
コンパイル使用メモリ | 219,112 KB |
実行使用メモリ | 12,288 KB |
最終ジャッジ日時 | 2024-05-09 17:12:32 |
合計ジャッジ時間 | 8,691 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 4 ms
5,376 KB |
testcase_05 | AC | 4 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | WA | - |
testcase_16 | AC | 4 ms
5,376 KB |
testcase_17 | WA | - |
testcase_18 | AC | 5 ms
5,376 KB |
testcase_19 | AC | 195 ms
7,420 KB |
testcase_20 | AC | 194 ms
7,424 KB |
testcase_21 | AC | 206 ms
7,420 KB |
testcase_22 | AC | 193 ms
7,424 KB |
testcase_23 | AC | 191 ms
7,424 KB |
testcase_24 | AC | 194 ms
7,424 KB |
testcase_25 | AC | 195 ms
7,424 KB |
testcase_26 | WA | - |
testcase_27 | AC | 195 ms
7,420 KB |
testcase_28 | AC | 194 ms
7,428 KB |
testcase_29 | AC | 186 ms
7,424 KB |
testcase_30 | AC | 194 ms
7,420 KB |
testcase_31 | AC | 196 ms
7,424 KB |
testcase_32 | AC | 190 ms
7,420 KB |
testcase_33 | AC | 193 ms
7,424 KB |
testcase_34 | AC | 276 ms
12,284 KB |
testcase_35 | AC | 283 ms
12,288 KB |
testcase_36 | AC | 151 ms
5,380 KB |
testcase_37 | WA | - |
testcase_38 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; template <typename T> constexpr T INF = numeric_limits<T>::max() / 16; template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "sz:" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template <typename Base> class BinaryIndexedTree { public: using T = typename Base::T; using AbelGroup = Base; BinaryIndexedTree(const int n) : data_num(n), size(1 << (__lg(2 * data_num - 1))), value(size + 1, AbelGroup::identity()) { assert(n > 0); } BinaryIndexedTree(const vector<T>& val) : data_num(val.size()), size(1 << (__lg(2 * data_num - 1))), value(size + 1, AbelGroup::identity()) { for (int i = 1; i <= data_num; i++) { value[i] = val[i - 1]; } for (int x = 1; x < size; x++) { value[x + (x & -x)] += value[x]; } } T accumulate(const int a) const { assert(0 <= a and a < data_num); int ind = a + 1; T sum = AbelGroup::identity(); while (ind > 0) { sum = op(sum, value[ind]); ind &= ind - 1; } return sum; } void add(const int a, const T& val) { assert(0 <= a and a < data_num); int ind = a + 1; while (ind <= size) { value[ind] = op(value[ind], val); ind += ind & (-ind); } } void set(const int a, const T& val) { const int v = get(a); add(a, op(val, op.inv(v))); } T get(const int a) const { assert(0 <= a and a < data_num); if (a == 0) { return accumulate(a); } else { return op(op.inv(accumulate(a - 1)), accumulate(a)); } } int lowerBound(T w) const { if (w <= AbelGroup::identity()) { return 0; } int x = 0; for (int k = ((size == data_num) ? size : size / 2); k > 0; k /= 2) { if (x + k <= size and value[x + k] < w) { w = op(w, op.inv(value[x + k])); x += k; } } return x; } int upperBound(T w) const { if (w <= AbelGroup::identity()) { return 0; } int x = 0; for (int k = ((size == data_num) ? size : size / 2); k > 0; k /= 2) { if (x + k <= size and value[x + k] <= w) { w = op(w, op.inv(value[x + k])); x += k; } } return min(x, data_num); } const int data_num; private: const int size; const AbelGroup op{}; vector<T> value; }; struct Sum { using T = int; T operator()(const T& a, const T& b) const { return a + b; } T inv(const T& a) const { return -a; } static constexpr T identity() { return 0; } }; ostream& operator<<(ostream& os, const BinaryIndexedTree<Sum>& bit) { os << "["; for (int i = 0; i < bit.data_num; i++) { os << bit.get(i) << ","; } os << "]" << endl; return os; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll Q; cin >> Q; using P = pair<int, ll>; vector<P> query(Q); vector<ll> comer{-INF<ll>}; ll offset = 0; //今までどれだけ底上げしたか for (int i = 0; i < Q; i++) { int t; ll x; cin >> t >> x; if (t == 1) { const ll power = x - offset; comer.push_back(power); query[i] = make_pair(t, power); } else if (t == 2) { const ll power = comer[x]; query[i] = make_pair(t, power); } else { offset += x; query[i] = make_pair(t, x); } } sort(comer.begin(), comer.end()); comer.erase(unique(comer.begin(), comer.end()), comer.end()); map<ll, int> mp; for (int i = 0; i < comer.size(); i++) { mp[comer[i]] = i; } const int size = comer.size(); BinaryIndexedTree<Sum> bit(size); offset = 0; int num = 0; for (const auto& q : query) { const int t = q.first; const ll x = q.second; if (t == 1) { bit.add(mp[x], 1); num++; } else if (t == 2) { bit.add(mp[x], -1); num--; } else { offset += x; } int inf = 0; int sup = size; while (inf < sup) { const int mid = (inf + sup) / 2; const int number = num - (mid == 0 ? 0 : bit.accumulate(mid - 1)); const ll value = offset + comer[mid]; if (value <= number) { if (inf == mid) { break; } inf = mid; } else { sup = mid; } } // show(comer); // show(offset); // show(bit); // show(inf); // show(sup); const int lnumber = num - (inf == 0 ? 0 : bit.accumulate(inf - 1)); const ll lvalue = offset + comer[inf]; const int rnumber = num - bit.accumulate(sup - 1); const ll rvalue = (sup == size ? INF<ll> : offset + comer[sup]); cout << max((int)lvalue, rnumber) << endl; } return 0; }