結果
| 問題 | No.2809 Sort Query |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2024-07-12 22:35:03 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,433 bytes |
| コンパイル時間 | 3,293 ms |
| コンパイル使用メモリ | 227,452 KB |
| 実行使用メモリ | 33,772 KB |
| 最終ジャッジ日時 | 2024-07-12 22:35:17 |
| 合計ジャッジ時間 | 13,304 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
13,760 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
vector<int> zaatu(vector<int> &A){
vector<int> B = A;
sort(B.begin(),B.end());
B.erase(unique(B.begin(),B.end()),B.end());
for(auto &a : A) a = lower_bound(B.begin(),B.end(),a)-B.begin();
return B;
}
vector<long long> zaatull(vector<long long> &A){
vector<long long> B = A;
sort(B.begin(),B.end());
B.erase(unique(B.begin(),B.end()),B.end());
return B;
}
using SS = int;
class SegmentTree{
public:
int siz = 1,n;
vector<SS> dat;
SS op(SS a, SS b){return a+b;}
SS e(){return 0;}
void renew (SS &a,SS x){
a = op(a,x);
//a = x;
//その他.
}
void make(int N){
while(siz < N) siz *= 2;
n = N; dat.resize(siz*2,e());
}
void make2(int N,vector<SS> &A){
make(N);
for(int i=0; i<N; i++){
int pos = i+siz;
dat.at(pos) = A.at(i);
}
for(int i=siz-1; i>0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1));
}
void update(int pos,SS x){
pos = pos+siz;
renew(dat.at(pos),x);
while(pos != 1){
pos = pos/2;
dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1));
}
}
SS findans(int l, int r){
SS retl = e(),retr = e();
l += siz,r += siz;
while(l < r){
if(l&1) retl = op(retl,dat.at(l++));
if(r&1) retr = op(dat.at(--r),retr);
l >>= 1; r >>= 1;
}
return op(retl,retr);
}
SS get(int pos){return dat.at(pos+siz);}
SS rangeans(int l, int r){return findans(l,r);}
SS allrange(){return dat.at(1);}
//rightは) leftは[で 渡す&返す.
int maxright(const function<bool(SS)> f,int l = 0){
l += siz; int r = n+siz;
vector<int> ls,rs;
while(l < r){
if(l&1) ls.push_back(l++);
if(r&1) rs.push_back(--r);
l >>= 1; r >>= 1;
}
SS okl = e();
for(int i=0; i<ls.size(); i++){
l = ls.at(i);
SS now = op(okl,dat.at(l));
if(!f(now)){
while(l < siz){
l <<= 1;
now = op(okl,dat.at(l));
if(f(now)){okl = now; l++;}
}
return l-siz;
}
okl = now;
}
for(int i=rs.size()-1; i>=0; i--){
l = rs.at(i);
SS now = op(okl,dat.at(l));
if(!f(now)){
while(l < siz){
l <<= 1;
now = op(okl,dat.at(l));
if(f(now)){okl = now; l++;}
}
return l-siz;
}
okl = now;
}
return n;
}
int minleft(const function<bool(SS)> f,int r = -1){
if(r == -1) r = n;
int l = siz; r += siz;
vector<int> ls,rs;
while(l < r){
if(l&1) ls.push_back(l++);
if(r&1) rs.push_back(--r);
l >>= 1; r >>= 1;
}
SS okr = e();
for(int i=0; i<rs.size(); i++){
r = rs.at(i);
SS now = op(dat.at(r),okr);
if(!f(now)){
while(r < siz){
r <<= 1; r++;
now = op(dat.at(r),okr);
if(f(now)){okr = now; r--;}
}
return r+1-siz;
}
}
for(int i=ls.size()-1; i>=0; i--){
r = ls.at(i);
SS now = op(dat.at(r),okr);
if(!f(now)){
while(r < siz){
r <<= 1; r++;
now = op(dat.at(r),okr);
if(f(now)){okr = now; r--;}
}
return r+1-siz;
}
}
return 0;
}
//ノーマルセグ木.一年の時を経て漸く二分探索実装した.
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,Q; cin >> N >> Q;
vector<long long> B(N,-1);
vector<int> St;
vector<long long> A(N),all;
for(auto &a : A) cin >> a;
all = A;
vector<tuple<int,long long,long long>> Query(Q,{-1,-1,-1});
for(auto &[t,k,x] : Query){
cin >> t;
if(t == 1) cin >> k >> x,k--,all.push_back(x);
if(t == 3) cin >> k,k--;
}
auto za = zaatull(all);
int n = za.size();
for(auto &a : A) a = lower_bound(za.begin(),za.end(),a)-za.begin();
for(auto &[t,k,x] : Query) if(t == 1) x = lower_bound(za.begin(),za.end(),x)-za.begin();
SegmentTree Z; Z.make(n);
for(auto &a : A) Z.update(a,1);
int border = -1;
auto f = [&](SS x){return x<border;};
bool sorted = false;
for(auto &[t,k,x] : Query){
if(t == 1){
St.push_back(k);
B.at(k) = x;
}
if(t == 2){
sorted = true;
for(auto pos : St){
if(B.at(pos) == -1) continue;
long long a1 = A.at(pos),a2 = B.at(pos);
Z.update(a1,-1); Z.update(a2,1);
B.at(pos) = -1;
}
}
if(t == 3){
if(B.at(k) != -1) cout << all.at(B.at(k)) << "\n";
else if(sorted == false) cout << all.at(A.at(k)) << "\n";
else{
border = k+1;
cout << all.at(Z.maxright(f)) << "\n";
}
}
}
}