Submission #320417

#	Time	Username	Problem	Language	Result	Execution time	Memory
320417		saarang123	Pilot (NOI19_pilot)	C++14	100 / 100	733 ms	76516 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1000 * 1000 + 3;
int par[N], sz[N];
int ans = 0;
bool u[N];

int cnt(int v) { return (v * (v + 1)) / 2; }

void init(int n) {
    for(int i = 0; i <= n + 1; i++) par[i] = i, sz[i] = 1;
}

int fin(int v) { return par[v] == v ? v : par[v] = fin(par[v]); }

void join(int a, int b) {
    if(!u[a] || !u[b]) return;
    a = fin(a); b = fin(b);
    if(a == b) return;
    ans -= cnt(sz[a]);
    ans -= cnt(sz[b]);
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
    ans += cnt(sz[a]);
}

void unite(int v) {
    u[v] = 1;
    ans += cnt(sz[v]);
    join(v, v + 1);
    join(v, v - 1);
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    int n, q;
    cin >> n >> q;
    init(n);
    vector<array<int, 2>> a(n), h(q);
    for(int i = 0; i < n; i++) cin >> a[i][0], a[i][1] = i + 1;
    for(int i = 0; i < q; i++) cin >> h[i][0], h[i][1] = i;
    sort(h.begin(), h.end());
    sort(a.begin(), a.end());
    vector<int> id(q);
    int j = 0;
    for(int i = 0; i < q; i++) {
        while(j < n && a[j][0] <= h[i][0]) {
            unite(a[j][1]);
            j++;
        }
        id[h[i][1]] = ans;
    }
    for(int i = 0; i < q; i++) cout << id[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