Submission #1270779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270779		hoangtien69	Pilot (NOI19_pilot)	C++20	100 / 100	426 ms	78528 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int long long 
const int MAXN = 1e6 + 5;

int n, q;
int h[MAXN], y[MAXN];
pii pos[MAXN];
pii query[MAXN];
int par[MAXN];
int sz[MAXN];
int total = 0;
int pidx = 1;
bool ck[MAXN];
int ans[MAXN];

int f(int x)
{
    return x * (x + 1) / 2;
}
void init()
{
    for (int i = 1; i <= n; i++)
    {
        par[i] = i;
        sz[i] = 0;
        ck[i] = false;
    }
}
int findd(int u)
{
    if (par[u] == u)
    {
        return par[u];
    }
    return par[u] = findd(par[u]);
}
bool join(int u, int v, int &total)
{
    u = findd(u);
    v = findd(v);
    if (u == v)
    {
        return false;
    }
    if (sz[u] < sz[v])
    {
        swap(u, v);
    }
    total -= f(sz[u]);
    total -= f(sz[v]);
    par[v] = u;
    sz[u] += sz[v];
    total += f(sz[u]);
    return true;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for (int i = 1; i <= q; i++)
    {
        cin >> y[i];
    }
    for (int i = 1; i <= n; i++)
    {
        pos[i].first = h[i];
        pos[i].second = i;
    }
    for (int i = 1; i <= q; i++)
    {
        query[i].first = y[i];
        query[i].second = i;
    }
    sort(pos + 1, pos + n + 1);
    sort(query + 1, query + q + 1);
    init();
    for (int i = 1; i <= q; i++)
    {
        int Y = query[i].first;
        int qi = query[i].second;
        while (pidx < n + 1 and pos[pidx].first <= Y)
        {
            int idx = pos[pidx].second;
            ck[idx] = true;
            sz[idx] = 1;
            total += 1;
            if (idx - 1 >= 1 and ck[idx - 1] == true)
            {
                join(idx - 1, idx, total);
            }
            if (idx + 1 <= n and ck[idx + 1] == true)
            {
                join(idx, idx + 1, total);
            }
            pidx++;
        }
        ans[qi] = total;
    }
    for (int i = 1; i <= q; i++)
    {
        cout << ans[i] << "\n";
    }
}

• 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