結果
| 問題 | No.3618 Omega Cat（Making ver.） |
| コンテスト | |
| ユーザー |
 Tamiji153
|
| 提出日時 | 2026-08-06 00:55:38 |
| 言語 | C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 339 ms / 2,000 ms |
| + 665µs | |
| コード長 | 15,810 bytes |
| 記録 | |
| コンパイル時間 | 5,423 ms |
| コンパイル使用メモリ | 403,876 KB |
| 実行使用メモリ | 36,552 KB |
| 最終ジャッジ日時 | 2026-08-06 13:40:03 |
| 合計ジャッジ時間 | 10,392 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 1 |
| 小課題1 | 20 % | AC * 5 |
| 小課題2 | 20 % | AC * 12 |
| 小課題3 | 40 % | AC * 24 |
| 小課題4 | 20 % | AC * 38 |
| 合計 | 3.5 * 100% = 350 点 |
コンパイルメッセージ
main.cpp: In function 'll3 td(const std::vector<std::vector<long long int> >&)':
main.cpp:337:20: warning: 'gl' may be used uninitialized [-Wmaybe-uninitialized]
337 | return {mx,st,gl};
| ^
main.cpp:332:13: note: 'gl' was declared here
332 | mx=-1;ll gl;
| ^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/vector:67,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/functional:81,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/x86_64-pc-linux-gnu/bits/stdc++.h:53,
from main.cpp:8:
In function '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = const long long int*; _ForwardIterator = long long int*]',
inlined from 'constexpr _ForwardIterator std::__uninitialized_copy_a(_InputIterator, _Sentinel, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = const long long int*; _Sentinel = const long long int*; _ForwardIterator = long long int*; _Tp = long long int]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_uninitialized.h:659:32,
inlined from 'constexpr void std::vector<_Tp, _Alloc>::_M_range_initialize_n(_Iterator, _Sentinel, size_type) [with _Iterator = const long long int*; _Sentinel = const long long int*; _Tp = long long int; _Alloc = std::allocator<long long int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_vector.h:1979:37,
inlined from 'constexpr std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_vector.h:702:23,
inlined from 'll3 td(const std::vector<std::vector<long long int> >&)' at main.cpp:331:7:
/home/linuxbrew/.linuxbrew/Cellar/gcc/16.1.0/include/c++/16/bits/stl_uninitialized.h:2
ソースコード
#ifdef __LOCAL
#define _GLIBCXX_DEBUG
#else
#ifdef __GNUC__
#pragma GCC optimize("O3")
#endif
#endif
#include<bits/stdc++.h>
#include<cassert>
using namespace std;
using uint=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using ld=long double;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define repr(i,n) for(ll i=(n)-1;i>=0;--i)
#define repa(i,a,b) for(ll i=(a);i<(b);++i)
#define repb(i,a,b) for(ll i=(b)-1;i>=(a);--i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define uniq(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
struct ll2{
ll a,b;
friend auto operator<=>(const ll2&,const ll2&)=default;
};
struct ll3{
ll a,b,c;
friend auto operator<=>(const ll3&,const ll3&)=default;
};
struct ll4{
ll a,b,c,d;
friend auto operator<=>(const ll4&,const ll4&)=default;
};
struct ll5{
ll a,b,c,d,e;
friend auto operator<=>(const ll5&,const ll5&)=default;
};
struct ll6{
ll a,b,c,d,e,f;
friend auto operator<=>(const ll6&,const ll6&)=default;
};
struct frac{
ll a,b;
friend auto operator<=>(frac a,frac b){
if(a.b==0&&b.b==0){
if(a.a>0&&b.a>0)return 0;
if(a.a<0&&b.a<0)return 0;
if(a.a>0&&b.a<0)return -1;
return 1;
}
if(a.b==0&&a.a>0)return -1;
if(b.b==0&&b.a>0)return 1;
if(a.b>=0&&b.b<=0)return -1;
if(a.b<=0&&b.b>=0)return 1;
if(a.a*b.b<a.b*b.a)return 1;
if(a.a*b.b==a.b*b.a)return 0;
return -1;
}
};
constexpr ll MOD=998244353LL;
constexpr ll MOD2=1000000007LL;
constexpr ll IMOD=11451445450721LL;
constexpr ll B10=1024LL;
constexpr ll B20=1048576LL;
constexpr ll B30=1073741824LL;
constexpr ll B40=1099511627776LL;
constexpr ll B50=1125899906842624LL;
constexpr ll B60=1152921504606846976LL;
constexpr ll INF=B60;
constexpr ll E3=1000LL;
constexpr ll E4=10000LL;
constexpr ll E5=100000LL;
constexpr ll E6=1000000LL;
constexpr ll E7=10000000LL;
constexpr ll E8=100000000LL;
constexpr ll E9=1000000000LL;
constexpr ll E10=10000000000LL;
constexpr ll E11=100000000000LL;
constexpr ll E12=1000000000000LL;
constexpr ll E13=10000000000000LL;
constexpr ll E14=100000000000000LL;
constexpr ll E15=1000000000000000LL;
constexpr ll E16=10000000000000000LL;
constexpr ll E17=100000000000000000LL;
constexpr ll E18=1000000000000000000LL;
constexpr ll2 D2[]={{0,1},{1,0}};
constexpr ll2 D4[]={{-1,0},{0,-1},{1,0},{0,1}};
constexpr ll2 D8[]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
constexpr char ALPH[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr char alph[]="abcdefghijklmnopqrstuvwxyz";
istream&operator>>(istream&is,i128&x){
ll y;is>>y;x=y;
return is;
}
ostream&operator<<(ostream&os,i128&x){
os<<static_cast<ll>(x);
return os;
}
ostream&operator<<(ostream&os,const ll2&o){
os<<o.a<<' '<<o.b;
return os;
}
ostream&operator<<(ostream&os,const ll3&o){
os<<o.a<<' '<<o.b<<' '<<o.c;
return os;
}
ostream&operator<<(ostream&os,const ll4&o){
os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d;
return os;
}
ostream&operator<<(ostream&os,const ll5&o){
os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d<<' '<<o.e;
return os;
}
ostream&operator<<(ostream&os,const ll6&o){
os<<o.a<<' '<<o.b<<' '<<o.c<<' '<<o.d<<' '<<o.e<<' '<<o.f;
return os;
}
// Print Vector
template<class T>
ostream&operator<<(ostream&os,const vector<T>&V){
for(auto a:V)os<<a<<' ';
return os;
}
// Print Set
template<class T>
ostream&operator<<(ostream&os,const set<T>&V){
for(auto a:V)os<<a<<' ';
return os;
}
// Print MultiSet
template<class T>
ostream&operator<<(ostream&os,const multiset<T>&V){
for(auto a:V)os<<a<<' ';
return os;
}
// Chmax
template<class T>
bool cmax(T&a,T b){
if(a<b){a=b;return 1;}
return 0;
}
// Chmin
template<class T>
bool cmin(T&a,T b){
if(a>b){a=b;return 1;}
return 0;
}
// Safe Division
ll dv(ll x,ll y){
if(x>0)return x/y;
return (x+((-x)/y+1)*y)/y-((-x)/y+1);
}
// Safe Mod
ll md(ll x,ll y){return x-y*dv(x,y);}
// Add and Mod
void madd(ll&a,ll b,ll mod=MOD){a=(md(a,mod)+md(b,mod))%mod;}
// Multiply and Mod
void mmul(ll&a,ll b,ll mod=MOD){a=md(a,mod)*md(b,mod)%mod;}
// Mod Power
ll mpow(ll x,ll y,ll mod=MOD){
if(y==0)return 1%mod;
ll t=mpow(x,y>>1,mod);
if(y&1)return t*t%mod*x%mod;
return t*t%mod;
}
// Extended GCD
ll2 egcd(ll a,ll b,ll t=1){
if(a>b){
auto[x,y]=egcd(b,a,t);
return {x,y};
}
if(!a)return {0,t/b};
auto[x,y]=egcd(b%a,a,t);
return {y-b/a*x,x};
}
// Mod Inversion
ll minv(ll x,ll mod=MOD){return md(egcd(x,mod).a,mod);}
// Identity Matrix
vector<vector<ll>> imat(ll n,ll mod=MOD){
vector X(n,vector<ll>(n,0));
rep(i,n)X[i][i]=1%mod;
return X;
}
// Matrix Prod
vector<vector<ll>> mtpr(vector<vector<ll>> X,vector<vector<ll>> Y,ll mod=MOD){
vector Z(X.size(),vector<ll>(Y[0].size(),0));
rep(i,X.size())rep(j,Y.size())rep(k,Y[0].size())Z[i][k]=(Z[i][k]+X[i][j]*Y[j][k])%mod;
return Z;
}
// Matrix Power
vector<vector<ll>> mtpw(vector<vector<ll>> X,ll n,ll mod=MOD){
if(!n)return imat(X.size(),mod);
if(n%2)return mtpr(mtpw(X,n-1,mod),X,mod);
auto Y=mtpw(X,n/2,mod);
return mtpr(Y,Y,mod);
}
// Factorial
pair<vector<ll>,vector<ll>> fact(ll n,ll mod=MOD,bool inv=true){
vector<ll> ans(n+1,1),ians(n+1);
rep(i,n)ans[i+1]=ans[i]*(i+1)%mod;
ians[n]=minv(ans[n],mod);
repr(i,n)ians[i]=ians[i+1]*(i+1)%mod;
return {ans,ians};
}
// Combination
ll comb(const vector<ll>&fct,const vector<ll>&ifct,ll n,ll r,ll mod=MOD){
if(r<0||n<r||n<0)return 0;
return fct[n]*ifct[r]%mod*ifct[n-r]%mod;
}
// Divisors
vector<ll> divs(ll n){
vector<ll> ans;
repa(i,1,static_cast<ll>(sqrt(static_cast<double>(n)))+1){
if(n%i==0){
ans.push_back(i);
if(i!=n/i)ans.push_back(n/i);
}
}
return ans;
}
// BFS
void bfs(const vector<vector<ll>>&G,vector<ll>&M,vector<ll> st){
queue<ll> Q;
for(ll s:st){
Q.push(s);
M[s]=0;
}
while(!Q.empty()){
ll p=Q.front();Q.pop();
for(ll q:G[p]){
if(M[p]+1<M[q]){
M[q]=M[p]+1;
Q.push(q);
}
}
}
}
// BFS with Parents
void bfsp(const vector<vector<ll>>&G,vector<ll>&M,vector<ll>&P,vector<ll> st){
queue<ll> Q;
for(ll s:st){
Q.push(s);
M[s]=0;
}
while(!Q.empty()){
ll p=Q.front();Q.pop();
for(ll q:G[p]){
if(M[p]+1<M[q]){
M[q]=M[p]+1;
P[q]=p;
Q.push(q);
}
}
}
}
// 0-1BFS
void bfs1(const vector<vector<ll2>>&G,vector<ll>&M,vector<ll> st){
deque<ll> Q;
for(ll s:st){
Q.push_back(s);
M[s]=0;
}
while(!Q.empty()){
ll p=Q.front();Q.pop_front();
for(auto[d,q]:G[p]){
if(M[p]+d<M[q]){
M[q]=M[p]+d;
if(d==1)Q.push_back(q);
else Q.push_front(q);
}
}
}
}
// Bellman-Ford
vector<ll> bf(ll n,const vector<ll3>&E,vector<ll> st){
vector<ll> dis(n,INF);
for(ll s:st)dis[s]=0;
rep(i,n)for(auto[w,u,v]:E)if(dis[v]>dis[u]+w)dis[v]=dis[u]+w;
for(auto[w,u,v]:E)if(dis[v]>dis[u]+w){
rep(i,n)dis[i]=-INF;
return dis;
}
return dis;
}
// Dijkstra
vector<ll> dij(const vector<vector<ll2>>&G,vector<ll> st){
ll n=G.size();
priority_queue<ll2,vector<ll2>,greater<>> Q;
vector<ll> dis(n,INF);
for(ll s:st){
Q.emplace(0,s);
dis[s]=0;
}
while(!Q.empty()){
auto[d,p]=Q.top();Q.pop();
if(d>dis[p])continue;
for(auto[e,q]:G[p]){
if(d+e<dis[q]){
dis[q]=d+e;
Q.emplace(d+e,q);
}
}
}
return dis;
}
// Warshall-Floyd
vector<vector<ll>> wf(const vector<vector<ll>>&G){
ll n=G.size();
vector dis(n,vector<ll>(n));
rep(i,n){
rep(j,n)dis[i][j]=G[i][j];
dis[i][i]=0;
}
rep(k,n)rep(i,n)rep(j,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
return dis;
}
// Tree Diamiter
ll3 td(const vector<vector<ll>>&G){
ll n=G.size();
vector<ll> M1(n,INF);
bfs(G,M1,{0});
ll mx=-1,st;
rep(i,n)if(M1[i]>mx){
mx=M1[i];
st=i;
}
vector<ll> M2(n,INF);
bfs(G,M2,{st});
mx=-1;ll gl;
rep(i,n)if(M2[i]>mx){
mx=M2[i];
gl=i;
}
return {mx,st,gl};
}
// Union-Find
struct uf{
vector<ll> par;
explicit uf(ll n):par(n,-1){}
ll find(ll u){
vector<ll> A;
while(par[u]>=0){
A.push_back(u);
u=par[u];
}
rep(i,A.size())par[A[i]]=u;
return u;
}
bool same(ll u,ll v){return find(u)==find(v);}
void merge(ll u,ll v){
u=find(u);
v=find(v);
if(u==v)return;
if(par[u]>par[v])swap(u,v);
par[u]+=par[v];
par[v]=u;
}
};
// Weighted Union-Find
struct wuf{
vector<ll> par;
vector<ll> dif;
explicit wuf(ll n):par(n,-1),dif(n){}
ll2 find(ll u){
vector<ll> A;
ll dis=0;
while(par[u]>=0){
A.push_back(u);
dis+=dif[u];
u=par[u];
}
ll sum=dis;
rep(i,A.size()){
par[A[i]]=u;
sum-=dif[A[i]];
dif[A[i]]+=sum;
}
return {u,dis};
}
bool same(ll u,ll v){return find(u).a==find(v).a;}
void merge(ll u,ll v,ll w){
auto[ur,ud]=find(u);
auto[vr,vd]=find(v);
if(ur==vr)return;
if(par[ur]>par[vr]){
swap(ur,vr);
w=-w;ud=-ud;vd=-vd;
}
par[ur]+=par[vr];
par[vr]=ur;
dif[vr]=w+ud-vd;
}
ll diff(ll u,ll v){return find(v).b-find(u).b;}
};
// Coordinate Compression
vector<ll> comp(const vector<ll>&A){
ll n=A.size();
set<ll> S;
for(ll a:A)S.insert(a);
vector<ll> T;
for(ll s:S)T.push_back(s);
vector<ll> ans(n);
rep(i,n)ans[i]=distance(T.begin(),lower_bound(all(T),A[i]));
return ans;
}
// MST
vector<ll3> mst(ll n,const vector<ll3>&E){
vector<ll3> F=E;sort(all(F));
uf U(n);
vector<ll3> ans;
for(auto[w,u,v]:F){
if(!U.same(u,v)){
U.merge(u,v);
ans.emplace_back(w,u,v);
}
}
return ans;
}
// Bipartite Coloring
vector<ll> bip(const vector<vector<ll>>&G){
ll n=G.size();
vector<ll> ans(n,-1);
bool ok=true;
rep(i,n){
if(ans[i]==-1){
ans[i]=0;
queue<ll> Q({i});
while(!Q.empty()){
ll p=Q.front();Q.pop();
for(ll q:G[p]){
if(ans[q]==-1){
ans[q]=ans[p]^1;
Q.push(q);
}else if(ans[q]==ans[p])ok=false;
}
}
}
}
if(!ok)ans[0]=-1;
return ans;
}
// Lowlink
pair<vector<ll>,vector<ll>> lowl(const vector<vector<ll>>&G,ll s){
ll n=G.size();
vector<ll> dis(n,-1),low(n);
dis[s]=0;
ll c=1;
auto dfs=[&](auto&&dfs,ll x)->ll{
for(ll y:G[x]){
if(dis[y]==-1){
dis[y]=c;low[y]=c;++c;
dfs(dfs,y);
low[x]=min(low[x],low[y]);
}else if(dis[y]<dis[x]-1)low[x]=min(low[x],dis[y]);
}
return 0;
};
dfs(dfs,s);
return {dis,low};
}
// Map with Default Value
template<class S,class T>
struct dmap:map<S,T>{
T def;
explicit dmap(T def):def(def){}
T&operator[](const S&i){return map<S,T>::emplace(i,def).first->second;}
};
// Min-Plus Convolution
vector<ll> mpc(vector<ll> X,vector<ll> Y){
vector<ll> R={X[0]+Y[0]};
ll a=0,b=0;while(1){
ll t=1;if(a==X.size()-1){
if(b==Y.size()-1)break;
else t=0;
}else{
if(b<Y.size()-1&&X[a+1]-X[a]>Y[b+1]-Y[b])t=0;
}if(t){R.push_back(R.back()+X[a+1]-X[a]);++a;}
else{R.push_back(R.back()+Y[b+1]-Y[b]);++b;}
}return R;
}
namespace atcoder {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
ll op(ll x,ll y){return max(x,y);}
ll e(){return -INF;}
ll slv(ll n,vector<ll> A){
A=comp(A);rep(i,n)++A[i];//cout<<A<<endl;
atcoder::segtree<ll,op,e> S(n+2),T(n+2),U(n+2),V(n+2),W(n+2);
S.set(n+1,0);S.set(A[0],1);repa(i,1,n){
ll t1=max(S.prod(A[i]+1,n+2),T.prod(A[i]+1,n+2))+1;
ll t2=max(S.prod(1,n+2),T.prod(1,n+2));
ll u1=max(T.prod(0,A[i]),U.prod(0,A[i]))+1;
ll u2=max(T.prod(0,n+1),U.prod(0,n+1));
ll v1=max(U.prod(A[i]+1,n+2),V.prod(A[i]+1,n+2))+1;
ll v2=max(U.prod(1,n+2),V.prod(1,n+2));
ll w1=max(V.prod(0,A[i]),W.prod(0,A[i]))+1;
ll w2=max(V.prod(0,n+1),W.prod(0,n+1));
T.set(A[i],t1);T.set(0,t2);
U.set(A[i],u1);U.set(n+1,u2);
V.set(A[i],v1);V.set(0,v2);
W.set(A[i],w1);W.set(n+1,w2);
}return n-W.all_prod();
}
int main(){
cin.tie(0)->sync_with_stdio(0);
ll t;cin>>t;while(t--){
ll n;cin>>n;
vector<ll> A(n);rep(i,n)cin>>A[i];
cout<<slv(n,A)<<'\n';}
}