Submission #548892

#	Time	Username	Problem	Language	Result	Execution time	Memory
548892		fadi57	Pilot (NOI19_pilot)	C++14	100 / 100	577 ms	75512 KiB

pilot

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int mx=1e6+9;

tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>s;
int n,q;
ll siz[mx],par[mx],a[mx],done[mx],anss[mx];
ll ans;
 void init(){
      for(int i=1;i<=n;i++){
        par[i]=i;
        siz[i]=1;
      }

}
int Find(int node){
   if(par[node]==node){
    return node;
   }
   return par[node]=Find(par[node]);
 }
 void uni(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x==y){return;}
     if(siz[x]>siz[y]){
        swap(x,y);
     }
 ans+=siz[x]*siz[y];
 par[x]=y;
 siz[y]+=siz[x];


 }
int main()
{
ios_base::sync_with_stdio(0);
    cin.tie(0);

    vector<pair<int,int>>v;
    vector<pair<int,int>>query;
    cin>>n>>q;
    init();
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        v.push_back({a[i],i});
    }
    sort(v.begin(),v.end());
    for(int i=0; i<q; i++)
    {   int x;
        cin>>x;
        query.push_back({x,i});
    }
     sort(query.begin(),query.end());
     int j=0;
     for(int i=0;i<q;i++){
        while(j<n&&v[j].first<=query[i].first){
            ans++;
            int idx=v[j].second;
            if(idx>0&&done[idx-1]){
                   // cout<<"TESR "<<idx<<endl;
                uni(idx-1,idx);
            }
            if(idx<n&&done[idx+1]){
                 uni(idx+1,idx);
            }
            j++;
            done[idx]=1;
        }
       // cout<<query[i].first<<" "<<query[i].second<<" "<<ans<<endl;
        anss[query[i].second]=ans;

     }
      for(int i=0;i<q;i++){
       cout<<anss[i]<<"\n";

     }


}

• 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