Submission #242833

#	Time	Username	Problem	Language	Result	Execution time	Memory
242833		gs18115	Pilot (NOI19_pilot)	C++14	100 / 100	939 ms	88652 KiB

pilot

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
int pa[1000010];
int par(int x)
{
    if(pa[x]==0)
        return x;
    return pa[x]=par(pa[x]);
}
ll cans;
ll sz[1000010];
inline void uni(int x,int y)
{
    x=par(x);
    y=par(y);
    if(x==y)
        return;
    cans-=sz[x]*(sz[x]+1)/2;
    cans-=sz[y]*(sz[y]+1)/2;
    pa[y]=x;
    sz[x]+=sz[y];
    cans+=sz[x]*(sz[x]+1)/2;
    return;
}
ll ans[1000010];
bool able[1000010];
vector<int>lst[1000010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int>v(n);
    for(int&t:v)
        cin>>t;
    v.insert(v.begin(),inf);
    for(int i=0;i++<n;)
        lst[v[i]].eb(i);
    for(int i=0;i++<1000000;)
    {
        for(int&t:lst[i])
        {
            able[t]=1;
            cans+=sz[t]=1;
            if(able[t-1])
                uni(t-1,t);
            if(able[t+1])
                uni(t,t+1);
        }
        ans[i]=cans;
    }
    while(q-->0)
    {
        int x;
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    cout.flush();
    return 0;
}

• 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