結果
| 問題 | No.3618 Omega Cat（Making ver.） |
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2026-08-06 20:28:44 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,725 bytes |
| 記録 | |
| コンパイル時間 | 2,014 ms |
| コンパイル使用メモリ | 232,264 KB |
| 実行使用メモリ | 19,592 KB |
| 最終ジャッジ日時 | 2026-08-06 20:29:05 |
| 合計ジャッジ時間 | 20,615 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 1 |
| 小課題1 | 20 % | WA * 5 |
| 小課題2 | 20 % | WA * 12 |
| 小課題3 | 40 % | WA * 24 |
| 小課題4 | 20 % | AC * 1 WA * 37 |
| 合計 | 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;
using FF = int;
class LazySegmentTree{
//ACL超参考にしてる というかパクリ.
//verify十分だけど注意.
private:
vector<SS> dat;
vector<FF> lazy;
public:
int siz = -1,n = -1,log = 0;
SS op(SS a,SS b){return min(a,b);}
SS mapping(FF f, SS x){return f+x;}
FF composition(FF f, FF g){return f+g;}
SS e(){return 1001001001;}
FF id(){return 0;}
//op区間演算 mapping lazy→data composition lazy→lazy
//e 単位元 id map(id,a)=a
LazySegmentTree(int N){init(N);}
LazySegmentTree(const vector<SS> &A){//配列サイズに合わせる.
siz = 1; n = A.size(); log = 0;
while(siz < n) siz <<= 1,log++;
dat.resize(siz*2,e());
lazy.resize(siz,id());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) merge(i);
}
void init(int N){ //単位元になる.
siz = 1; n = N; log = 0;
while(siz < n) siz *= 2,log++;
dat.assign(siz*2,e());
lazy.assign(siz,id());
}
void init(const vector<SS> &A){ //配列サイズに合わせる.
siz = 1; n = A.size(); log = 0;
while(siz < n) siz <<= 1,log++;
dat.resize(siz*2,e());
lazy.assign(siz,id());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) merge(i);
}
private:
void eval(int u,FF f){
//u番目にfを適用したあと保留.
if(u == 0) return;
dat.at(u) = mapping(f,dat.at(u));
if(u < siz) lazy.at(u) = composition(f,lazy.at(u));
}
void spread(int u){ //uにあるFF保留を伝播.
if(u == 0 || id() == lazy.at(u)) return;
eval(2*u,lazy.at(u));
eval(2*u+1,lazy.at(u));
lazy.at(u) = id();
}
void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ.
public:
void set(int pos,SS x){ //1点変更.
assert(0 <= pos && pos < n);
pos += siz;
for(int i=log; i>0; i--) spread(pos>>i);
dat.at(pos) = x;
while(pos > 1) pos >>= 1,merge(pos);
}
void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!.
assert(0 <= pos && pos < n);
pos += siz;
for(int i=log; i>0; i--) spread(pos>>i);
dat.at(pos) = mapping(f,dat.at(pos));
while(pos > 1) pos >>= 1,merge(pos);
}
void update(int l,int r,FF f){ //区間更新.
assert(0 <= l && l <= r && r <= n);
if(l == r) return;
l += siz; r += siz;
for(int i=log; i>0; i--){
if(((l>>i)<<i) != l) spread(l>>i);
if(((r>>i)<<i) != r) spread((r-1)>>i);
}
int memoL = l,memoR = r;
while(l < r){
if(l&1) eval(l++,f);
if(r&1) eval(--r,f);
l >>= 1; r >>= 1;
}
l = memoL,r = memoR;
while((l&1) == 0) l >>= 1;
while((r&1) == 0) r >>= 1;
r--; //-1注意.
while(l > 1) l >>= 1,merge(l);
while(r > 1) r >>= 1,merge(r);
}
SS get(int pos){ //1点取得.
assert(0 <= pos && pos < n);
pos += siz;
for(int i=log; i>0; i--) spread(pos>>i);
return dat.at(pos);
}
SS rangeans(int l,int r){ //区間取得.
assert(0 <= l && l <= r && r <= n);
if(l == r) return e();
l += siz; r += siz;
for(int i=log; i>0; i--){
if(((l>>i)<<i) != l) spread(l>>i);
if(((r>>i)<<i) != r) spread((r-1)>>i);
}
SS retl = e(),retr = e();
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 allrange(){return dat.at(1);} //全体取得.
int maxright(const function<bool(SS)> f,int l = 0){
assert(0 <= l && l <= n && f(e()));
if(l == n) return n;
l += siz;
for(int i=log; i>0; i--) spread(l>>i);
SS now = e();
do{
while(l%2 == 0) l >>= 1;
SS next = op(now,dat.at(l));
if(f(next) == false){
while(l < siz){
spread(l); l <<= 1;
next = op(now,dat.at(l));
if(f(next)) now = next,l++;
}
return l-siz;
}
now = next; l++;
}while((l&-l) != l);
return n;
}
int minleft(const function<bool(SS)> f,int r = -1){
if(r == -1) r = n;
assert(0 <= r && r <= n && f(e()));
if(r == 0) return 0;
r += siz;
for(int i=log; i>0; i--) spread((r-1)>>i);
SS now = e();
do{
r--;
while(r&1) r >>= 1;
if(r == 0) r = 1;
SS next = op(dat.at(r),now);
if(f(next) == false){
while(r < siz){
spread(r);
r <<= 1; r++;
next = op(dat.at(r),now);
if(f(next)) now = next,r--;
}
return r+1-siz;
}
now = next;
}while((r&-r) != r);
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<LazySegmentTree> Z(4,LazySegmentTree(N+2));
auto chmin = [&](auto &a,auto b) -> void {a=min(a,b);};
Z.at(0).set(H.at(0),0);
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) = p-1;
for(int t=0; t<4; t++){
if(t%2 == 0){
chmin(now.at(t),Z.at(t).rangeans(h,N));
if(p > 1) chmin(now.at(t+1),Z.at(t).rangeans(0,h));
}
else{
if(t != 3) chmin(now.at(t+1),Z.at(t).rangeans(h,N));
chmin(now.at(t),Z.at(t).rangeans(0,h));
}
}
if(p > 1){
for(int t=0; t<3; t++){
if(t%2 == 0) Z.at(t+1).set(N+1,min(Z.at(t+1).get(N+1),Z.at(t).get(0)));
else Z.at(t+1).set(0,min(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=0; t<4; t++){
int now = Z.at(t).get(H.at(q));
if(t < 3) Z.at(t+1).set(H.at(q),min(Z.at(t+1).get(H.at(q)),now));
if(t%2 == 0){
Z.at(t).set(0,min(Z.at(t).get(0),now));
Z.at(t+1).set(N+1,min(Z.at(t+1).get(N+1),now));
}
else{
if(t < 3) Z.at(t+1).set(0,min(Z.at(t+1).get(0),now));
Z.at(t).set(N+1,min(Z.at(t).get(N+1),now));
}
}
}
}
for(int i=0; i<4; i++) Z.at(i).update(0,N+2,1);
for(int i=0; i<4; i++) Z.at(i).set(h,now.at(i));
}
cout << Z.at(3).allrange() << "\n";
}
}