Submission #344741

#	Time	Username	Problem	Language	Result	Execution time	Memory
344741		nguot	Pilot (NOI19_pilot)	C++14	100 / 100	944 ms	97516 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0)
#define fori(x,a,b) for (int x=a;x<=b;x++)
#define ford(x,a,b) for (int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f, x, sizeof(f))
#define getbit(x,i) ((x>>(i-1))&1)
#define batbit(x,i) (x|(1ll<<(i-1)))
#define tatbit(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int maxn = 1e6 + 10;
int n,t,x,dd[maxn];
vector<int> ke[maxn];
ii q[maxn];
int f[maxn];

int root(int x)
{
    if(f[x]<0) return x;
    return f[x] = root(f[x]);
}

int kq=0;
void hop(int x,int y)
{
   if(!dd[y]||y>n||y<1) return;

   x = root(x),y = root(y);
   kq-=(f[x]*(f[x]-1) + f[y]*(f[y]-1))/2;
   f[y]+=f[x];
   f[x] = y;
   kq+=f[y]*(f[y]-1)/2;
}

int ans[maxn];
main()
{
    //freopen("task.inp","r",stdin);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>t;
    fori(i,1,n) cin>>x,ke[x].pb(i);
    fori(i,1,t) cin>>q[i].fi,q[i].se = i;
    sort(q+1,q+t+1);

    reset(f,-1);
    int m=1;
    fori(i,1,1e6)
    {
       forv(j,ke[i])
       {
           ++kq,dd[j] = 1;
           hop(j,j+1),hop(j,j-1);
       }
       while(q[m].fi==i) ans[q[m].se] = kq,++m;
    }
    fori(i,1,t) cout<<ans[i]<<"\n";

}

Compilation message (stderr)

pilot.cpp:47:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      |      ^

• 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