Submission #484078

#	Time	Username	Problem	Language	Result	Execution time	Memory
484078		CyberSleeper	Pilot (NOI19_pilot)	C++14	100 / 100	696 ms	35024 KiB

pilot

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL)
#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<int, int>
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

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

int N, Q, Y, H[MX];
ll tot=0, ans[MX];
pii A[MX];

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

int main(){
    fastio;
    cin >> N >> Q;
    for(int i=0; i<N; i++){
        cin >> H[i];
        A[i]={H[i], i};
    }
    sort(A, A+N);
    for(int i=0; i<N; i++){
        tot++;
        int h=A[i].fi, idx=A[i].se;
        if(idx && H[idx-1]<=h)
            DSU.join(idx-1, idx);
        if(idx+1<N && H[idx+1]<=h)
            DSU.join(idx+1, idx);
        ans[i]=tot;
    }
    for(int i=0; i<Q; i++){
        cin >> Y;
        cout << ans[upper_bound(A, A+N, mp(Y, INF))-A-1] << nl;
    }
}

• 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