QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#65149#4593. Darkmoon Fairezzxzzx123Compile Error//C++205.0kb2022-11-27 19:43:502022-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]
  • 评测
  • [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>
      | ^~~~~~~