Submission #1187232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187232		aladdin1	Pilot (NOI19_pilot)	C++20	100 / 100	459 ms	69772 KiB

pilot

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,base=31,inf=1e9,mxN=1e3+5,L=21;
int ans=0;
struct DSU{
    vector<int>par,sz;
    DSU(int n){
        par.resize(n+1),sz.resize(n+1);
        for(int i=0;i<=n;i++)par[i]=i,sz[i]=1;
    }
    
    int root(int x){
        return (par[x]==x)?x:(par[x]=root(par[x]));
    }
    void unite(int a,int b){
        a=root(a),b=root(b);
        if(a==b)return;
        ans-=(sz[a]*(sz[a]+1))/2;
        ans-=(sz[b]*(sz[b]+1))/2;
        if(sz[a]<sz[b])swap(a,b);
        par[b]=a,sz[a]+=sz[b];
        ans+=(sz[a]*(sz[a]+1))/2;
    }
};
void solve(){
    int n,q;cin>>n>>q;
    vector<int>b(n),cvb(q);
    vector<pair<int,int>>v1,v;
    for(int i=0;i<n;i++)cin>>b[i],v1.push_back({b[i],i});
    for(int i=0;i<q;i++){
        int x;cin>>x;
        v.push_back({x,i});
    }
    sort(v1.begin(),v1.end());
    sort(v.begin(),v.end());
    DSU dsu(n+1);
    int idx=0;
    for(int i=0;i<q;i++){
        while(idx<n&&v1[idx].first<=v[i].first){
            ans++;
            if(v1[idx].second>0&&b[v1[idx].second-1]<=v1[idx].first)dsu.unite(v1[idx].second,v1[idx].second-1);
            if(v1[idx].second+1<n&&b[v1[idx].second+1]<=v1[idx].first)dsu.unite(v1[idx].second,v1[idx].second+1);
            idx++;
        }
        cvb[v[i].second]=ans;
    }
    
    for(int i=0;i<q;i++){
        cout<<cvb[i]<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;//cin>>t;
    while(t--){
      solve();
    }
}

• 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