Submission #1359096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1359096		kanapojpm	Pilot (NOI19_pilot)	C++20	100 / 100	539 ms	71384 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> p;
vector<int> sz;
int sum=0;
int find_p(int u){
    if(p[u]==u)return u;
    return p[u]=find_p(p[u]);
}
signed main(){
    int n,m;
    cin >> n >> m;
    p.resize(n);
    sz.resize(n);
    for(int i=0;i<n;i++){
        p[i]=i;
        sz[i]=1;
    }
    vector<int> h(n);
    vector<pair<int,int>> lis;
    for(int i=0;i<n;i++){
        cin >> h[i];
        lis.push_back({h[i],i});
    }
    vector<pair<int,int>> pl;
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        int y;
        cin >> y;
        pl.push_back({y,i});
    }
    sort(lis.begin(),lis.end());
    sort(pl.begin(),pl.end());
    int idx=0;
    //for(int i=0;i<pl.size();i++) cout << pl[i].first << " " << pl[i].second << "\n";
    for(int i=0;i<pl.size();i++){
        // for(int j=0;j<n;j++){
        //     cout << sz[find_p()]
        // }
        int val = pl[i].first;
        while(idx<lis.size()&&lis[idx].first<=val){
            int idx2 = lis[idx].second;
            int s=1;
            if(idx2-1>=0&&h[idx2-1]<=lis[idx].first){
                int p1 = find_p(idx2-1);
                int p2 = find_p(idx2);                
                if(p1!=p2){                
                    //cout << "-" << sz[p1] << " ";
                    sum-=(sz[p1]*(sz[p1]-1)/2) + sz[p1];
                    s+=sz[p1];
                    if(sz[p1]>sz[p2]){
                        p[p2]=p1;
                        sz[p1]+=sz[p2];
                    }
                    else{
                        p[p1]=p2;
                        sz[p2]+=sz[p1];
                    }
                }
            }
            if(idx2+1<n&&h[idx2+1]<lis[idx].first){
                int p1 = find_p(idx2+1);
                int p2 = find_p(idx2);
                if(p1!=p2){
                    //cout << "-" << sz[p1] << " ";
                    sum-=(sz[p1]*(sz[p1]-1)/2) + sz[p1];
                    s+=sz[p1];
                    if(sz[p1]>sz[p2]){
                        p[p2]=p1;
                        sz[p1]+=sz[p2];
                    }
                    else{
                        p[p1]=p2;
                        sz[p2]+=sz[p1];
                    }
                }
            }
            sum+=(s*(s-1)/2) + s;
            //cout << s << " " << sum << "\n";
            idx++;
        }
        //cout << "\n";
        //cout << sum;
        ans[pl[i].second] = sum;
    }
    for(int i=0;i<ans.size();i++)
        cout << ans[i] << " ";
}

• 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