Submission #552565

#	Time	Username	Problem	Language	Result	Execution time	Memory
552565		RaresFelix	Pilot (NOI19_pilot)	C++17	100 / 100	590 ms	60252 KiB

pilot

#include <bits/stdc++.h>
#define MN 1000071

using namespace std;
int n, q, A[MN], On[MN];
using ll = long long;
ll rez;
vector<pair<int, int> > Ord;

int P[MN], S[MN];

void init() {
    for(int i = 0; i < MN; ++i)
        S[i] = 1, P[i] = i;
}

int repr(int u) {
    return P[u] == u ? u : (P[u] = repr(P[u]));
}

void uni(int u, int v) {
    u = repr(u), v = repr(v);
    if(u == v) return;
    if(S[u] < S[v]) swap(u, v);
    rez -= 1ll * S[v] * (S[v] + 1) / 2;
    rez -= 1ll * S[u] * (S[u] + 1) / 2;
    S[u] += S[v];
    rez += 1ll * S[u] * (S[u] + 1) / 2;
    P[v] = u;
}

void activ(int p) {
    On[p] = 1, ++rez;
    if(On[p + 1]) uni(p, p + 1);
    if(On[p - 1]) uni(p, p - 1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    init();
    for(int i = 1; i <= n; ++i) {
        cin >> A[i];
        Ord.push_back({A[i], i});
    }
    sort(Ord.begin(), Ord.end());
    vector<pair<int, int> > Q;
    for(int i = 1, a; i <= q; ++i) {
        cin >> a;
        Q.push_back({a, i-1});
    }
    sort(Q.begin(), Q.end());
    vector<ll> R(q);
    auto it = Q.begin();
    for(auto [a, b] : Ord) {
        while(it != Q.end() && it->first < a)
            R[it->second] = rez, ++it;
        activ(b);
    }
    while(it != Q.end()) R[it->second] = rez, ++it;
    for(auto i : R) cout << i << "\n";
    return 0;
}

• 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