Submission #485435

#	Time	Username	Problem	Language	Result	Execution time	Memory
485435		blue	Pilot (NOI19_pilot)	C++17	100 / 100	987 ms	52124 KiB

pilot

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;

const int mx = 1'000'000;

vi H;

long long ans = 0;

vi parent(mx);
vi subtree(mx, 1);

int root(int u)
{
    if(parent[u] == u) return u;
    else
    {
        parent[u] = root(parent[u]);
        return parent[u];
    }
}

long long ch(long long v)
{
    return v*(v+1)/2;
}

int N, Q;

void join(int u, int v)
{
    if(v < 0 || N <= v) return;
    if(!subtree[v]) return;

    u = root(u);
    v = root(v);
    if(u == v) return;

    if(subtree[u] < subtree[v]) swap(u, v);

    ans += ch(subtree[u] + subtree[v]) - ch(subtree[u]) - ch(subtree[v]);

    parent[v] = u;
    subtree[u] += subtree[v];
}

int main()
{
    cin >> N >> Q;

    H = vi(N+Q);
    vi I(N+Q);
    for(int i = 0; i < N+Q; i++)
    {
        cin >> H[i];
        I[i] = i;
    }

    for(int i = 0; i < N+Q; i++) I[i] = i;

    sort(I.begin(), I.end(), [] (int p, int q)
    {
        if(H[p] != H[q]) return H[p] < H[q];
        else return p < q;
    });


    for(int i = 0; i < N; i++)
    {
        parent[i] = i;
        subtree[i] = 0;
    }

    vector<long long> res(Q);


    for(int i:I)
    {
        if(i < N)
        {
            ans++;
            subtree[i] = 1;
            join(i, i-1);
            join(i, i+1);
        }
        else
        {
            res[i-N] = ans;
        }
    }

    for(int j = 0; j < Q; j++) cout << res[j] << '\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