Submission #484103

#	Time	Username	Problem	Language	Result	Execution time	Memory
484103		CyberSleeper	Pilot (NOI19_pilot)	C++14	100 / 100	443 ms	69956 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=1000007, MOD=1e9+7, BLOCK=330, INF=1e9+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

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

ll readll(){
	bool minus=false;
	ll result=0;
	char ch;
	ch=getchar();
	while(true){
		if(ch=='-')
            break;
		if(ch>='0' && ch<='9')
            break;
		ch=getchar();
	}
	if(ch=='-')
        minus=true;
    else
        result = ch-'0';
	while(true){
		ch=getchar();
		if(ch<'0' || ch>'9')
            break;
		result=result*10+(ch-'0');
	}
	if(minus)
		return -result;
	else
		return result;
}
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(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    N=readll();
    Q=readll();
    for(ll i=0; i<N; i++){
        H[i]=readll();
        A[i]={H[i], i};
    }
    for(ll i=0; i<Q; i++){
        Y[i].fi=readll();
        Y[i].se=i;
    }
    sort(Y, Y+Q);
    sort(A, A+N);
    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++){
        cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

pilot.cpp: In function 'long long int readll()':
pilot.cpp:39:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   39 |     else
      |     ^~~~
pilot.cpp:41:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   41 |  while(true){
      |  ^~~~~

• 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