제출 #999102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999102		fryingduc	Pilot (NOI19_pilot)	C++17	100 / 100	397 ms	68948 KiB

pilot

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

const int maxn = 1e6 + 5;
int n, q;
pair<int, int> y[maxn];
pair<int, int> h[maxn];
int par[maxn], sz[maxn];
long long total[maxn];
bool check[maxn];
long long ans[maxn], res[maxn];

struct dsu {
    int n;
    dsu() {}
    dsu(int n) : n(n) {
        for(int i = 1; i <= n; ++i) {
            sz[i] = 1;
            par[i] = i;
            total[i] = 1;
        }
    }
    int find(int u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }
    void join(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return;
        par[v] = u;
        total[u] += total[v];
        total[u] += 1ll * sz[u] * sz[v];
        sz[u] += sz[v];
    }
};
void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> h[i].first;
        h[i].second = i;
    }
    for(int i = 1; i <= q; ++i) {
        cin >> y[i].first;
        y[i].second = i;
    }
    sort(h + 1, h + n + 1);
    sort(y + 1, y + q + 1);
    
    dsu d(n);
    
    int j = 0;
    long long sum = 0;
    for(int i = 1; i <= n; ++i) {
        int cur = 0;
        while(i + cur <= n and h[i].first == h[i + cur].first) {
            if(check[h[i + cur].second - 1]) {
                sum -= total[d.find(h[i + cur].second - 1)];
                d.join(h[i + cur].second, h[i + cur].second - 1);
            }
            if(check[h[i + cur].second + 1]) {
                sum -= total[d.find(h[i + cur].second + 1)];   
                d.join(h[i + cur].second, h[i + cur].second + 1);
            }
            
            sum += total[d.find(h[i + cur].second)];
            check[h[i + cur].second] = 1;
            ++cur;
        }
        
        while(j <= q and y[j].first < h[i].first) ++j;
        ans[j] = sum;
        i = i + cur - 1;
    }
    
    for(int i = 1; i <= q; ++i) {
        ans[i] = max(ans[i], ans[i - 1]);
        res[y[i].second] = ans[i];
    }
    for(int i = 1; i <= q; ++i) {
        cout << res[i] << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    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