結果
| 問題 | No.3618 Omega Cat（Making ver.） |
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2026-08-06 21:35:47 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,954 bytes |
| 記録 | |
| コンパイル時間 | 1,458 ms |
| コンパイル使用メモリ | 228,200 KB |
| 実行使用メモリ | 14,596 KB |
| 最終ジャッジ日時 | 2026-08-06 21:35:57 |
| 合計ジャッジ時間 | 8,881 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | WA * 1 |
| 小課題1 | 20 % | WA * 5 |
| 小課題2 | 20 % | WA * 12 |
| 小課題3 | 40 % | WA * 24 |
| 小課題4 | 20 % | WA * 38 |
| 合計 | 3.5 * 0% = 0 点 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template<typename T>
vector<T> zaatu(vector<T> &A){
//座標圧縮=Compress.
vector<T> 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;
}
using SS = int;
class SegmentTree{
public:
int siz = -1,n = -1;
vector<SS> dat;
SS op(SS a, SS b){return max(a,b);}
SS e(){return -1001001001;}
void renew (SS &a,SS x){
a = op(a,x);
//a = x; //set(pos,x)で可能.
//その他.
}
SegmentTree(int N){init(N);}
SegmentTree(const vector<SS> &A){//長さ配列サイズに合わせる.
siz = 1; n = A.size();
while(siz < n) siz *= 2;
dat.resize(siz*2,e());
for(int i=0; i<n; i++) dat.at(i+siz) = 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 init(int N){
//全要素単位元に初期化.
siz = 1; n = N;
while(siz < n) siz *= 2;
dat.assign(siz*2,e());
}
void init(const vector<SS> &A){//長さ配列サイズに合わせる.
siz = 1; n = A.size();
while(siz < n) siz *= 2;
dat.resize(siz*2,e());
for(int i=0; i<n; i++) dat.at(i+siz) = 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 set(int pos,SS x){
pos = pos+siz;
dat.at(pos) = x;
while(pos != 1){
pos = pos/2;
dat.at(pos) = op(dat.at(pos*2),dat.at(pos*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){
//fを満たさない最小の箇所を返す なければn.
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){
//fを満たす最小の箇所を返す なければ0.
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;
}
okr = now;
}
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;
}
okr = now;
}
return 0;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while(T--){
int N; cin >> N;
vector<int> H(N);
for(auto &h : H) cin >> h;
zaatu(H);
for(auto &h : H) h++;
vector<SegmentTree> Z(4,SegmentTree(N+2));
auto chmax = [&](auto &a,auto b) -> void {a=max(a,b);};
Z.at(0).set(H.at(0),1);
for(int p=1; p<N; p++){
int h = H.at(p);
vector<int> now(4,-1001001001);
for(int i=0; i<min(4,p); i++) now.at(i) = 1;
for(int t=0; t<4; t++){
if(t%2 == 0){
chmax(now.at(t),Z.at(t).rangeans(h,N+2)+1);
if(p > 1) chmax(now.at(t+1),Z.at(t).rangeans(0,h)+1);
}
else{
if(t != 3) chmax(now.at(t+1),Z.at(t).rangeans(h,N+2)+1);
chmax(now.at(t),Z.at(t).rangeans(0,h)+1);
}
}
for(int t=2; t>=0; t--){
if(t%2 == 0) Z.at(t+1).set(N+1,max(Z.at(t+1).get(N+1),Z.at(t).get(0)));
else Z.at(t+1).set(0,max(Z.at(t+1).get(0),Z.at(t).get(N+1)));
}
for(int q=p-1; q>=p-5; q--){
if(q < 0) break;
for(int t=3; t>=0; t--){
int now = Z.at(t).get(H.at(q));
if(p > 1 && t < 3) Z.at(t+1).set(H.at(q),max(Z.at(t+1).get(H.at(q)),now));
if(t%2 == 0){
Z.at(t).set(0,max(Z.at(t).get(0),now));
if(p > 1) Z.at(t+1).set(N+1,max(Z.at(t+1).get(N+1),now));
}
else{
if(t < 3) Z.at(t+1).set(0,max(Z.at(t+1).get(0),now));
Z.at(t).set(N+1,max(Z.at(t).get(N+1),now));
}
}
}
continue;
for(int i=0; i<4; i++) Z.at(i).set(h,now.at(i));
cout << p+1 << " " << h+1 << endl;
for(int t=0; t<4; t++){
for(int i=0; i<N+2; i++){
int now = Z.at(t).get(i);
if(now <= -1000001001) cout << "-";
else cout << now;
}
cout << endl;
}
}
cout << N-Z.at(3).allrange() << "\n";
}
}