Submission #895891

#	Time	Username	Problem	Language	Result	Execution time	Memory
895891		kh0i	Pilot (NOI19_pilot)	C++17	100 / 100	472 ms	88628 KiB

pilot

#include "bits/stdc++.h"
using namespace std;

using ll = long long;

const int N = 1e6 + 3;

int n, q, h[N], y[N];

namespace Sub12348{
    bool valid_input() { return n * q <= 1e7; }

    void solve(){
        for(int t = 1; t <= q; ++t){
            ll cur = 0, res = 0;
            for(int i = 1; i <= n; ++i){
                if(h[i] <= y[t])
                    ++cur;
                else{
                    res += cur * (cur + 1) / 2;
                    cur = 0;
                }
            }
            res += cur * (cur + 1) / 2;
            cout << res << '\n';
        }
    }
}

namespace Sub5{
    bool valid_input(){ return q == 1 and y[1] == 1e6; }
    void solve() { cout << 1ll * n * (n + 1) / 2; }
}

namespace Sub67{
    bool valid_input(){
        bool ok = 1;
        for(int i = 2; i <= n; ++i)
            ok &= (h[i] > h[i - 1]);
        return ok;
    }

    void solve(){
        for(int t = 1; t <= q; ++t){
            ll x = upper_bound(h + 1, h + n + 1, y[t]) - h;
            cout << x * (x + 1) / 2 << '\n';
        }
    }
}

struct DSU{
    vector<ll> p;
    ll cur;

    void init(int n){
        p.resize(n + 2, 0);
        cur = 0;
    }

    ll calc(ll x) { return x * (x + 1) / 2; }
    void make_set(int u){
        ++cur;
        p[u] = -1;
    }
    int find_set(int u) { return p[u] < 0 ? u : p[u] = find_set(p[u]); }
    void join_sets(int u, int v){
        u = find_set(u);
        v = find_set(v);
        if(u == v)
            return;
        cur -= calc(-p[u]);
        cur -= calc(-p[v]);
        if(p[u] > p[v])
            swap(u, v);
        p[u] += p[v];
        p[v] = u;
        cur += calc(-p[u]);
    }
} dsu;

bool ok[N];
vector<int> to_add[N];
ll res[N];

namespace SubFull{
    void solve(){
        dsu.init(N);
        for(int i = 1; i <= n; ++i)
            to_add[h[i]].push_back(i);
        for(int i = 1; i < N; ++i){
            for(int j = 0; j < (int)to_add[i].size(); ++j){
                int x = to_add[i][j];
                dsu.make_set(x);
                if(ok[x - 1])
                    dsu.join_sets(x - 1, x);
                if(ok[x + 1])
                    dsu.join_sets(x, x + 1);
                ok[x] = 1;
            }
            res[i] = dsu.cur;
        }

        for(int i = 1; i <= q; ++i)
            cout << res[y[i]] << '\n';
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        cin >> h[i];
    for(int i = 1; i <= q; ++i)
        cin >> y[i];

    SubFull::solve();

    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