結果
問題 |
No.2809 Sort Query
|
ユーザー |
|
提出日時 | 2024-07-12 22:54:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 817 ms / 2,000 ms |
コード長 | 3,730 bytes |
コンパイル時間 | 2,523 ms |
コンパイル使用メモリ | 190,820 KB |
実行使用メモリ | 38,320 KB |
最終ジャッジ日時 | 2024-07-12 22:55:29 |
合計ジャッジ時間 | 49,055 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
コンパイルメッセージ
main.cpp: In function 'void solve()': main.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 108 | for(auto [type, k, x] : query){ | ^
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i) #define rep(i, n) drep(i, 0, n - 1) #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; template<typename T> struct fenwick_tree{ int n; vector<T> dat; // constractor fenwick_tree(){} fenwick_tree(int n) : n(n){ dat.resize(n+1, 0); } /* - return sum in range [0, i] - query time : O(log n) */ T sum(int i){ T s = 0; while(i > 0){ s += dat[i]; i -= i & -i; } return s; } /* - return sum in range [l, r) - query time : O(log n) */ T sum(int l, int r){ return sum(r) - sum(l); } /* - add x to dat[i+1] - processing time : O(log n) */ void add(int i, T x){ i++; while(i <= n){ dat[i] += x; i += i & -i; } } }; void solve(){ int n, q; cin >> n >> q; vector<ll> a(n); for(int i=0; i<n; i++) cin >> a[i]; vector<tuple<int, int, ll>> query(q+n); for(int i=0; i<n; i++){ query[i] = {1, i, a[i]}; a[i] = 0; } q += n; for(int i=n; i<q; i++){ int type; cin >> type; if(type == 1){ int k; ll x; cin >> k >> x; query[i] = {1, k-1, x}; } if(type == 2){ query[i] = {2, -1, -1}; } if(type == 3){ int k; cin >> k; query[i] = {3, k-1, -1}; } } int siz = 0; vector<ll> comp; for(int i=0; i<q; i++) comp.pb(get<2>(query[i])); sort(all(comp)); comp.erase(unique(all(comp)), comp.end()); for(int i=0; i<q; i++){ int tmp = lower_bound(all(comp), get<2>(query[i])) - comp.begin(); query[i] = {get<0>(query[i]), get<1>(query[i]), tmp}; } siz = (int)comp.size(); fenwick_tree<int> ft1(siz), ft2(n); ft1.add(0, n); set<int> st; for(auto [type, k, x] : query){ if(type == 1){ if(a[k] == 0){ int cnt = k+1 - ft2.sum(0, k+1); int lo = 0, mid, hi = siz-1; while(hi - lo > 1){ mid = (lo + hi)/2; if(cnt <= ft1.sum(0, mid+1)) hi = mid; else lo = mid; } ft1.add(hi, -1); st.insert(k); ft2.add(k, 1); } a[k] = x; } if(type == 2){ for(auto idx : st){ ft1.add(a[idx], 1); ft2.add(idx, -1); a[idx] = 0; } set<int> new_st; st = new_st; } if(type == 3){ int ans = 0; if(a[k] != 0){ ans = a[k]; }else{ int cnt = k+1 - ft2.sum(0, k+1); int lo = 0, mid, hi = siz-1; while(hi - lo > 1){ mid = (lo + hi)/2; if(cnt <= ft1.sum(0, mid+1)) hi = mid; else lo = mid; } ans = hi; } cout << comp[ans] << '\n'; } } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int T=1; //cin >> T; while(T--) solve(); }