QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#65149 | #4593. Darkmoon Faire | zzxzzx123 | Compile Error | / | / | C++20 | 5.0kb | 2022-11-27 19:43:50 | 2022-11-27 19:43:52 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2022-11-27 19:43:52]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2022-11-27 19:43:50]
- 提交
answer
include<iostream>
#include<cstdio>
#define For(i,a,b) for(int i=a;i<=b;i++)
const long long mod=998244353;
const int N=3e5+1000;
int stack[2][N],top[2];//上升,下降
int a[N];
long long dp[N];
long long sum[4*N][2][2][2];//开始位置为偶/奇,min假设/实际 max假设/实际、
long long tag[4*N][2][2];//开始位置为 偶/奇,min/max的奇偶性改变为tag
inline void Push_up(int root,int odd)
{
For(j,0,1) For(k,0,1)
{
sum[root][odd][j][k]=(sum[root<<1][odd][j][k]+sum[root<<1|1][odd][j][k]);
if (sum[root][odd][j][k]>mod) sum[root][odd][j][k]-=mod;
}
}
inline void pushdown(int root,int l,int r,int odd)
{
For(opt,0,1)
{
if (tag[root][odd][opt]==-1) continue;
int v=tag[root][odd][opt];
// printf("?? %d %d %d %d %d %d\n",root,l,r,odd,opt,v);
if (opt==0) //min
{
if (v!=odd)
{
sum[root][odd][1][1]=sum[root][odd][0][1];
sum[root][odd][1][0]=sum[root][odd][0][0];
}
else
{
sum[root][odd][1][1]=0;
sum[root][odd][1][0]=0;
}
}
else//max
{
if (v==odd)
{
sum[root][odd][1][1]=sum[root][odd][1][0];
sum[root][odd][0][1]=sum[root][odd][0][0];
}
else
{
sum[root][odd][1][1]=0;
sum[root][odd][0][1]=0;
}
}
if (l!=r) tag[root<<1][odd][opt]=tag[root<<1|1][odd][opt]=tag[root][odd][opt];
tag[root][odd][opt]=-1;
}
}
inline void Push_down(int root,int l,int r,int odd)
{
if (l==r) return ;
int mid=(l+r)>>1;
pushdown(root<<1,l,mid,odd);
pushdown(root<<1|1,mid+1,r,odd);
}
void Build(int root,int l,int r)
{
if (l==r)
{
tag[root][0][0]=tag[root][0][1]=tag[root][1][0]=tag[root][1][1]=-1;
For(i,0,1) For(j,0,1) For(k,0,1) sum[root][i][j][k]=0;
return ;
}
int mid=(l+r)>>1;
Build(root<<1,l,mid);Build(root<<1|1,mid+1,r);
tag[root][0][0]=tag[root][0][1]=tag[root][1][0]=tag[root][1][1]=-1;
For(i,0,1) For(j,0,1) For(k,0,1) sum[root][i][j][k]=0;
}
void update(int root,int l,int r,int a,int b,int odd,int opt,int v)
{
Push_down(root,l,r,odd);
if (l==a&&r==b)
{
tag[root][odd][opt]=v;
pushdown(root,l,r,odd);
return ;
}
int mid=(l+r)>>1;
if (b<=mid) update(root<<1,l,mid,a,b,odd,opt,v);
else
{
if (a>mid) update(root<<1|1,mid+1,r,a,b,odd,opt,v);
else update(root<<1,l,mid,a,mid,odd,opt,v),update(root<<1|1,mid+1,r,mid+1,b,odd,opt,v);
}
Push_up(root,odd);
}
void insert(int root,int l,int r,int x,int odd)
{
Push_down(root,l,r,odd);
if (l==r)
{
(sum[root][odd][0][0]+=dp[2*x+odd-1])%=mod;
return ;
}
int mid=(l+r)>>1;
if (x<=mid) insert(root<<1,l,mid,x,odd);
else insert(root<<1|1,mid+1,r,x,odd);
sum[root][odd][0][0]=(sum[root<<1][odd][0][0]+sum[root<<1|1][odd][0][0])%mod;
return ;
}
void read(int &x)
{
x=0;int flag=1;
char c=getchar();
while (c<'0'||c>'9')
{
if (c=='-') flag=-1;
c=getchar();
}
while ('0'<=c&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
x*=flag;
}
int main()
{
int T;read(T);
while (T--)
{
int n;read(n);For(i,1,n+1) dp[i]=0;dp[0]=1;
Build(1,0,n>>1);
top[1]=top[0]=0;
For(i,1,n)
{
read(a[i]);
// a[i]=i&1?i:-i;
insert(1,0,n>>1,i>>1,i&1);
while (top[0]>0&&a[stack[0][top[0]]]>=a[i]) top[0]--;stack[0][++top[0]]=i;
while (top[1]>0&&a[stack[1][top[1]]]<=a[i]) top[1]--;stack[1][++top[1]]=i;
int L,R;
L=stack[0][top[0]-1]+1;R=i;
if (!(L&1)) L++;if (!(R&1)) R--;
if (L<=R) update(1,0,n>>1,L>>1,R>>1,1,0,i&1);//min=a[i]: L= stack[0][top[0]-1]+1 ~ i 开始位置为奇数
// printf("?? %d %d\n",L,R);
L=stack[1][top[1]-1]+1;R=i;
if (!(L&1)) L++;if (!(R&1)) R--;
if (L<=R) update(1,0,n>>1,L>>1,R>>1,1,1,i&1);//max=a[i]: L= stack[1][top[1]-1]+1 ~ i 开始位置为奇数
// printf("?? %d %d\n",L,R);
L=stack[0][top[0]-1]+1;R=i;
if (L&1) L++;if (R&1) R--;
if (L<=R) update(1,0,n>>1,L>>1,R>>1,0,0,i&1);//min=a[i]: L= stack[0][top[0]-1]+1 ~ i 开始位置为偶数
// printf("?? %d %d\n",L,R);
L=stack[1][top[1]-1]+1;R=i;
if (L&1) L++;if (R&1) R--;
if (L<=R) update(1,0,n>>1,L>>1,R>>1,0,1,i&1);//max=a[i]: L= stack[1][top[1]-1]+1 ~ i 开始位置为偶数
// printf("?? %d %d\n",L,R);
dp[i]=(sum[1][0][1][1]+sum[1][1][1][1])%mod;
// printf("!! %d %lld\n",i,dp[i]);
}
printf("%lld\n",dp[n]);
}
return 0;
}
详细
answer.code:1:9: error: ‘iostream’ was not declared in this scope 1 | include<iostream> | ^~~~~~~~ answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:9: error: ‘iostream’ was not declared in this scope answer.code:1:1: error: ‘include’ does not name a type 1 | include<iostream> | ^~~~~~~