Submission #471626

#	Time	Username	Problem	Language	Result	Execution time	Memory
471626		ToroTN	Pilot (NOI19_pilot)	C++14	100 / 100	874 ms	79632 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
int n,m,a,chk[1000005],p[1000005],node,fuck;
long long cnt=0,ans[1000005],l,r;
vector<int> v[1000005];
int f(int a)
{
    if(p[a]==a)
    {
        return a;
    }
    return p[a]=f(p[a]);
}
void un(int b,int c)
{
    chk[f(c)]+=chk[f(b)];
    p[f(b)]=f(c);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        v[a].push_back(i);
        chk[i]=1;
    }
    for(int i=1;i<=1000000;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            node=v[i][j];
            chk[node]=1;
            p[node]=node;
            l=(long long)(chk[f(node-1)]);
            r=(long long)(chk[f(node+1)]);
            if(l==0&&r==0)
            {
                cnt+=1;
            }else if(l==0)
            {
                cnt+=r+(long long)1;
            }else if(r==0)
            {
                cnt+=l+(long long)1;
            }else
            {
                cnt+=(l+(long long)1)*(r+(long long)1);
            }
            //printf("%lld\n",cnt);
            if(p[node-1]!=0)
            {
                un(node-1,node);
            }
            if(p[node+1]!=0)
            {
                un(node+1,node);
            }
            /*for(int k=1;k<=n;k++)
            {
                printf("%d ",chk[f(k)]);
            }
            printf("\n\n");*/
        }
        ans[i]=cnt;
    }
    while(m--)
    {
        scanf("%d",&fuck);
        printf("%lld\n",ans[fuck]);
    }
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
pilot.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
pilot.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~
pilot.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d",&fuck);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11