結果
問題 |
No.2809 Sort Query
|
ユーザー |
![]() |
提出日時 | 2024-07-13 11:08:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 799 ms / 2,000 ms |
コード長 | 3,265 bytes |
コンパイル時間 | 6,262 ms |
コンパイル使用メモリ | 321,832 KB |
実行使用メモリ | 34,216 KB |
最終ジャッジ日時 | 2024-07-13 11:09:26 |
合計ジャッジ時間 | 47,301 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
コンパイルメッセージ
In constructor 'FenwickTree::FenwickTree(int)', inlined from 'int main()' at main.cpp:77:29: main.cpp:25:17: warning: 'bit.FenwickTree::size' may be used uninitialized [-Wmaybe-uninitialized] 25 | size += sz; | ^~~~ main.cpp: In function 'int main()': main.cpp:77:21: note: 'bit' declared here 77 | FenwickTree bit(comp.size()); | ^~~
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n) - 1; i >= 0; --i) #define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define P pair<int,int> template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } struct FenwickTree { vector<int> tree; int size; int start; FenwickTree(int sz) { size += sz; tree.resize(size + 1); start = 0; while ((1 << (start + 1)) <= size)start++; } void add(int pos, int val) { pos++; while (pos <= size) { tree[pos] += val; pos += pos & -pos; } } int bisect(int pos) { int now = 0; int val = 0; for (int i = start; i >= 0; i--) { if (now + (1 << i) <= size && val + tree[now + (1 << i)] <= pos) { now += 1 << i; val += tree[now]; } } return now; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<long long>a(n); rep(i, n)cin >> a[i]; struct Query { int t; int k; long long x; Query(int t = -1, int k = -1, long long x = -1) :t(t), k(k), x(x) {} void output() { std::cout << t << " " << k << " " << x << endl; } }; vector<long long>comp = a; vector<Query>query(q); rep(i, q) { cin >> query[i].t; if (3 == query[i].t) cin >> query[i].k; else if (1 == query[i].t) { cin >> query[i].k >> query[i].x; comp.push_back(query[i].x); } } sort(all(comp)); comp.erase(unique(all(comp)), comp.end()); //fenwick_tree<int> bit(comp.size()); FenwickTree bit(comp.size()); rep(i, q) { if (1 == query[i].t) { query[i].x = lower_bound(all(comp), query[i].x) - comp.begin(); } } vector<long long>change(n, -1); vector<pair<long long, long long>>chq; vector<int>upd; rep(i, n) { a[i] = lower_bound(all(comp), a[i]) - comp.begin(); change[i] = a[i]; upd.push_back(i); } bit.add(0, n); auto f = [&](int x)->int { return bit.bisect(x); /*int ok = 0; int ng = comp.size(); while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; bool chk = bit.sum(0, mid) <= x; if (chk)ok = mid; else ng = mid; } return ok;*/ }; rep(i, q) { int t = query[i].t; int k = query[i].k; int x = query[i].x; if (1 == t) { change[k - 1] = x; upd.push_back(k - 1); } else if (2 == t) { while (!upd.empty()) { if (-1 != change[upd.back()]) { int pos = f(upd.back()); chq.push_back({ pos,change[upd.back()] }); change[upd.back()] = -1; } upd.pop_back(); } while (!chq.empty()) { auto[f, s] = chq.back(); bit.add(f, -1); bit.add(s, 1); chq.pop_back(); } } else { if (-1 != change[k - 1]) { cout << comp[change[k - 1]] << endl; } else { cout << comp[f(k - 1)] << endl; } } } return 0; }