QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#307777#8016. 不休陀螺jerry2007Compile Error//C++143.0kb2024-01-19 09:08:382024-01-19 09:08:38

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 09:08:38]
  • 评测
  • [2024-01-19 09:08:38]
  • 提交

answer

# include<bits/stdc++.h>
# define lowbit(x) (x&(-x))
# define N 1000005
#define int long long
using namespace std;
int a[N],b[N];
int sum1[N],sum2[N],maxa[N];
int n,E;
int ans;
bool mark[N];
struct BIT
{
    int sum[N],k;
    void init(int x)
    {
        k=x;
        for(int i=1;i<=x;i++)
            sum[i]=0;
    }
    void add(int x,int y)
    {
        for(int i=x;i<=k;i+=lowbit(i))
            sum[i]+=y;
    }
    int query(int x)
    {
        int ans=0;
        for(int i=x;i>0;i-=lowbit(i))
            ans+=sum[i];
        return ans;
    }
}T;
struct node
{
    int x,id;
}p[N],del[N];
int cnt;
signed rk[N];
bool cmp(node x,node y)
{
    return x.x<y.x;
}
void solve(int l,int r)
{
    if(l==r) 
    {
        ans+=a[l]<=E && b[l]>=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    sum1[mid]=max(0ll,a[mid]-b[mid]);
    sum1[mid+1]=max(0ll,a[mid+1]-b[mid+1]);
    maxa[mid]=min(a[mid],b[mid]),maxa[mid+1]=min(a[mid+1],b[mid+1]);
    for(int i=mid-1;i>=l;i--)
    {
        sum1[i]=sum1[i+1]+max(0ll,a[i]-b[i]);
        maxa[i]=max(maxa[i+1],min(a[i],b[i]));
    }
    for(int i=mid+2;i<=r;i++)
    {
        sum1[i]=sum1[i-1]+max(0ll,a[i]-b[i]);
        maxa[i]=max(maxa[i-1],min(a[i],b[i]));
    }

    cnt=0;
    p[++cnt]=(node){sum2[l-1],l-1};
    for(int i=l;i<=r;i++)
        p[++cnt]=(node){sum2[i],i}; 
    sort(p+1,p+1+cnt,cmp);
    int now=0;
    for(int i=1;i<=cnt;i++) 
    {
        if(i==1 || p[i-1].x!=p[i].x)
            now++;
        rk[p[i].id]=now;
    }
    T.init(now);
    for(int i=mid+1;i<=r;i++)
        T.add(rk[i],1),mark[i]=1,del[i-mid]=(node){sum1[i]+maxa[i],i};
    sort(del+1,del+r-mid+1,cmp);
    int p1=mid+1,p2=r-mid,res=r-mid;
    for(int i=mid;i>=l;i--)
    {
        while(p1<=r && maxa[p1]<maxa[i])
        {
            if(mark[p1]) T.add(rk[p1],-1),res--;
            mark[p1]=0,p1++;
        }
        while(p2 && E-sum1[i]<del[p2].x)
        {
            int x=del[p2].id;
            if(mark[x])
                T.add(rk[x],-1),res--;
            mark[x]=0;
            p2--;
        }
        ans+=res-T.query(rk[i-1]-1); 
    }

    T.init(now);
    for(int i=l;i<=mid;i++)
        T.add(rk[i-1],1),mark[i]=1,del[i-l+1]=(node){sum1[i]+maxa[i],i};
    sort(del+1,del+1+mid-l+1,cmp);
    p1=mid,p2=mid-l+1;
    for(int i=mid+1;i<=r;i++)
    {
        while(p1>=l && maxa[p1]<=maxa[i])
        {
            if(mark[p1]) T.add(rk[p1-1],-1);
            mark[p1]=0,p1--;
        }
        while(p2 && E-sum1[i]<del[p2].x)
        {
            int x=del[p2].id;
            if(mark[x])
                T.add(rk[x-1],-1);
            mark[x]=0;
            p2--;
        }
        ans+=T.query(rk[i]); 
    }
}
signed main()
{=
    cin>>n>>E;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        sum2[i]=sum2[i-1]+b[i]-a[i];
    solve(1,n);
    cout<<ans<<endl;
    return 0;
}

詳細信息

answer.code: In function ‘int main()’:
answer.code:126:2: error: expected primary-expression before ‘=’ token
  126 | {=
      |  ^
answer.code:129:17: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
  129 |         scanf("%d",&a[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  long long int*
      |                 int*
      |                %lld
answer.code:131:17: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
  131 |         scanf("%d",&b[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  long long int*
      |                 int*
      |                %lld
answer.code:129:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  129 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
answer.code:131:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  131 |         scanf("%d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~