Submission #484089

#	Time	Username	Problem	Language	Result	Execution time	Memory
484089		CyberSleeper	Pilot (NOI19_pilot)	C++14	100 / 100	579 ms	70004 KiB

pilot

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define pll         pair<ll, ll>
#define ull         unsigned long long
#define ld          long double
#define pii         pair<ll, ll>
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=1000001, MOD=1e9+7, BLOCK=330, INF=1e9+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

ll N, Q, ptr=0;
vector<ll> H, ans;
ll tot=0;
vector<pii> A, Y;

ll calc(ll x){
    return x*(1ll+x)/2ll;
}
struct dsu{
    ll par[MX], sz[MX];
    dsu(){
        for(ll i=0; i<MX; i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    ll f(ll u){
        if(par[u]!=u)
            par[u]=f(par[u]);
        return par[u];
    }
    void join(ll u, ll v){
        u=f(u);
        v=f(v);
        if(u==v)
            return;
        if(sz[u]>sz[v])
            swap(u, v);
        tot-=calc(sz[u])+calc(sz[v]);
        par[u]=v;
        sz[v]+=sz[u];
        tot+=calc(sz[v]);
    }
}DSU;

int main(){
    fastio;
    scanf("%lld", &N);
    scanf("%lld", &Q);
    H.resize(N);
    A.resize(N);
    Y.resize(Q);
    ans.resize(Q);
    for(ll i=0; i<N; i++){
        scanf("%lld", &H[i]);
        A[i]={H[i], i};
    }
    for(ll i=0; i<Q; i++){
        scanf("%lld", &Y[i].fi);
        Y[i].se=i;
    }
    sort(Y.begin(), Y.end());
    sort(A.begin(), A.end());
    for(ll i=0; ptr<Q && i<N; i++){
        ll h=A[i].fi, idx=A[i].se;
        while(ptr<Q && Y[ptr].fi<h)
            ans[Y[ptr++].se]=tot;
        if(ptr>=Q)
            break;
        tot++;
        if(idx && H[idx-1]<=h)
            DSU.join(idx-1, idx);
        if(idx+1<N && H[idx+1]<=h)
            DSU.join(idx+1, idx);
    }
    while(ptr<Q)
        ans[Y[ptr++].se]=tot;
    for(ll i=0; i<Q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
pilot.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%lld", &Q);
      |     ~~~~~^~~~~~~~~~~~
pilot.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%lld", &H[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
pilot.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%lld", &Y[i].fi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• 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