Submission #334970

#	Time	Username	Problem	Language	Result	Execution time	Memory
334970		Dymo	Pilot (NOI19_pilot)	C++14	100 / 100	616 ms	68716 KiB

pilot

#include<bits/stdc++.h>
using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e6+10;
const ll mod =1e9+7 ;
const ll base=3e18;
ll par[maxn];
ll n;
bool dd[maxn];
ll find_par(ll u)
{
  //  cout <<u<<endl;
    if (par[u]<0) return u;
    return par[u]=find_par(par[u]);

}
ll ans=0;
void ad(ll x )
{
   ans+=((x)*(x+1)/2);
}
void er(ll x )
{
  //  cout <<x<<x*(x+1)/2<<endl;

   ans=ans-((x)*(x+1)/2);
   //cout <<x<<endl;
}
void add(ll x)
{
    dd[x]=1;
    if (x==1)
    {
        if (dd[x+1])
        {
           ll t=find_par(x+1);
           er(-par[t]);
           ad(-par[t]+1);
           par[t]+=par[x];
           par[x]=t;
        }
        else
        {
              ans+=(-par[x]);
        }
    }
    else if (x==n)
    {
         if (dd[x-1])
        {
          ll t=find_par(x-1);
          //cout <<t<<" "<<-par[t]<<endl;
        //  cout <<"WTF"<<endl;
            er(-par[t]);

         ad(-par[t]+1);
        //  cout <<t<<endl;
           par[t]+=par[x];
           par[x]=t;
         //  cout <<t<<endl;*/
        }
        else
        {
               ans+=(-par[x]);
        }
    }
    else
    {
        if (dd[x+1]&&dd[x-1])
        {
            ll t=find_par(x+1);
            er(-par[t]);
           par[t]+=par[x];
         //  ad(-par[t]);
           par[x]=t;
           ll h=find_par(x-1);
           er(-par[h]);
           par[t]+=par[h];
           ad(-par[t]);
           par[h]=t;
        }
        else if (dd[x-1])
        {
             ll t=find_par(x-1);
            er(-par[t]);
           ad(-par[t]+1);
           par[t]+=par[x];
           par[x]=t;
        }
        else if (dd[x+1])
        {
            ll t=find_par(x+1);
           er(-par[t]);
           ad(-par[t]+1);
           par[t]+=par[x];
           par[x]=t;
        }
        else
        {
            ans+=(-par[x]);
        }
    }
}
ll ans1[maxn];
pll a[maxn];
pll h[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("harbingers.in", "r"))
    {
        freopen("harbingers.in", "r", stdin);
        freopen("harbingers.out", "w", stdout);
    }
  ll q;
     cin>> n>>q ;
     for (int i=1;i<=n;i++) par[i]=-1;
     for (int i=1;i<=n;i++)
     {
         cin>>h[i].ff;
         h[i].ss=i;
     }
     sort(h+1,h+n+1);
     for (int i=1;i<=q;i++)
     {
         cin>>a[i].ff;
         a[i].ss=i;
     }
     sort(a+1,a+q+1);
     ll st=1;
     for (int i=1;i<=q;i++)
     {
         while (st<=n&&h[st].ff<=a[i].ff)
         {
            add(h[st].ss);
        //   cout <<st<<" "<<n<<" "<<h[st].ss<<" "<<ans<<endl;
             st++;
         }
      //   cout <<a[i].ss<<" "<<ans<<endl;
         ans1[a[i].ss]=ans;
     }
     for (int i=1;i<=q;i++)
     {
         cout <<ans1[i]<<endl;
     }






}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  123 |         freopen("harbingers.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  124 |         freopen("harbingers.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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