結果
問題 |
No.2809 Sort Query
|
ユーザー |
|
提出日時 | 2024-07-12 21:51:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,761 ms / 2,000 ms |
コード長 | 4,062 bytes |
コンパイル時間 | 2,850 ms |
コンパイル使用メモリ | 186,152 KB |
最終ジャッジ日時 | 2025-02-22 03:53:14 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <algorithm> #include <cmath> #include <iomanip> #include <random> #include <stdio.h> #include <fstream> #include <functional> #include <cassert> #include <unordered_map> #include <bitset> #include <chrono> #include <atcoder/modint> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace atcoder; using namespace __gnu_pbds; using mint = modint1000000007; #define rep(i,n) for (int i=0;i<n;i+=1) #define rrep(i,n) for (int i=n-1;i>-1;i--) #define pb push_back #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n"; template<class T> using vec = vector<T>; template<class T> using vvec = vec<vec<T>>; template<class T> using vvvec = vec<vvec<T>>; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<class T> bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template<class T> bool chmax(T &a, T b){ if (a<b){ a = b; return true; } return false; } template<class T> T sum(vec<T> x){ T res=0; for (auto e:x){ res += e; } return res; } template<class T> void printv(vec<T> x){ for (auto e:x){ cout<<e<<" "; } cout<<endl; } template<class T,class U> ostream& operator<<(ostream& os, const pair<T,U>& A){ os << "(" << A.first <<", " << A.second << ")"; return os; } template<class T> ostream& operator<<(ostream& os, const set<T>& S){ os << "set{"; for (auto a:S){ os << a; auto it = S.find(a); it++; if (it!=S.end()){ os << ", "; } } os << "}"; return os; } template<class T> ostream& operator<<(ostream& os, const tuple<T,T,T>& a){ auto [x,y,z] = a; os << "(" << x << ", " << y << ", " << z << ")"; return os; } template<class T> ostream& operator<<(ostream& os, const map<ll,T>& A){ os << "map{"; for (auto e:A){ os << e.first; os << ":"; os << e.second; os << ", "; } os << "}"; return os; } template<class T> ostream& operator<<(ostream& os, const vec<T>& A){ os << "["; rep(i,A.size()){ os << A[i]; if (i!=A.size()-1){ os << ", "; } } os << "]" ; return os; } ostream& operator<<(ostream& os, const mint& a){ os << a.val(); return os; } void solve(){ int N,Q; cin>>N>>Q; vec<ll> A(N); rep(i,N) cin>>A[i]; tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> sorted_val_set; set<int> update_idx = {}; rep(i,N){ update_idx.insert(i); } map<int,ll> update_val; rep(i,N){ update_val[i] = A[i]; } rep(i,N){ sorted_val_set.insert({ll(i),ll(i)}); } int nxt = N; while (Q--){ int t; cin>>t; if (t == 1){ int k;ll x; cin>>k>>x; k--; if (!update_idx.count(k)){ update_idx.insert(k); } update_val[k] = x; } else if (t == 2){ int tmp = 0; //debug(update_idx); //assert (sorted_val_set.size() == N); for (auto i:update_idx){ auto [val,x] = *sorted_val_set.find_by_order(i-tmp); //debug(make_pair(val,x)); sorted_val_set.erase({val,x}); tmp++; //sorted_val_set.insert({update_val[i],i}); //for (auto [a,b]:sorted_val_set){ //cout << a << " " << b << "\n"; //} } for (auto i:update_idx){ sorted_val_set.insert({update_val[i],ll(nxt)}); nxt++; } update_idx.clear(); update_val.clear(); } else{ int k; cin>>k; k--; if (!update_idx.count(k)){ auto [val,x] = *sorted_val_set.find_by_order(k); cout << val << "\n"; } else{ cout << update_val[k] << "\n"; } } } } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); int T = 1; while (T--){ solve(); } }