Submission #1295188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295188		kqhuy2009	Pilot (NOI19_pilot)	C++20	78 / 100	32 ms	4652 KiB

pilot

#include <bits/stdc++.h>
#define ll int
#define INF (ll)1e9+1
#define bit(mask, id) ((mask >> id) & 1LL)
#define flip(mask, id) (mask ^ (1LL << id))
#define onbit(mask, id) (mask  (1LL << id))
#define offbit(mask,id) (mask & ~(1LL << id))
#define pb push_back
#define el '\n'
#define ft first
#define sc second
#define fi first
#define se second
#define ii pair<ll,ll>
#define FOR(i, l, r) for (ll i = (ll)(l); i <= (ll)(r); i++)
#define FORD(i, l, r) for(ll i = (ll)(l); i >= (ll)(r); i--)
#define str string
#define all(a,i) memset(a,i,sizeof(a))
/////////////////////////////

const long long oo = 1e18;
const int N = 1e6 + 9;

using namespace std;

ll par[N], sz[N];
ll acs(ll u)
{
    if(par[u] == u) return u;
    return par[u] = acs(par[u]);
}
void join(ll x, ll y)
{
    ll u = acs(x);
    ll v = acs(y);
    if(u==v) return;
    if(sz[u]<sz[v]) swap(u,v);
    par[v] = u;
    sz[u] += sz[v];
}
ll n;
ii a[N];
ll Q;
long long ans[N];
ii q[N];
bool vis[N];
signed main()
{
    #define TASK "pilot"
    if(fopen(TASK ".inp","r")) {
        freopen (TASK ".inp","r",stdin);
        freopen (TASK ".out","w",stdout);
        //freopen (TASK ".ans","w",stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>Q;
    FOR(i,1,n+1) par[i] = i;
    FOR(i,1,n)
    {
        cin>>a[i].ft;
        a[i].sc = i;
    }
    sort(a+1,a+1+n);
    FOR(i,1,Q)
    {
        cin>>q[i].ft;
        q[i].sc = i;
    }
    sort(q+1,q+1+Q);
    long long res = 0;
    ll j = 0;
    FOR(i,1,Q)
    {
        ll x = q[i].ft;
        while(a[j+1].ft <= x && j+1<=n)
        {
            j++;
            ll id = a[j].sc;

            sz[id]++;
            res += sz[acs(id-1)];
            res += sz[acs(id+1)];
            res += sz[acs(id-1)] * sz[acs(id+1)];
            res++;

            if(vis[id-1]) join(id,id-1);
            if(vis[id+1]) join(id,id+1);

            vis[id] = 1;
        }
        ans[q[i].sc] = res;
    }
    FOR(i,1,Q) cout<<ans[i]<<el;
    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:51:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen (TASK ".inp","r",stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:52:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen (TASK ".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: 0 / 11
• Subtask 10: 0 / 11