제출 #1267272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267272		nguyenvietanh	Pilot (NOI19_pilot)	C++20	100 / 100	399 ms	69896 KiB

pilot

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define inp(name) freopen(name, "r", stdin);
#define out(name) freopen(name, "w", stdout);
const int N = 1e6 + 5;
const int mod = 998244353;
int n, q, ans = 0;
pii h[N], x[N];
int par[N], sz[N], res[N], ok[N];
int find(int u){
    if (par[u] == u) return u;
    return par[u] = find(par[u]);
}
void add(int u, int v){
    u = find(u), v = find(v);
    if (u == v) return;
    par[u] = v;
    ans -= (sz[u] + 1) * sz[u]/2;
    ans -= (sz[v] + 1) * sz[v]/2;
    sz[v] += sz[u];
    ans += (sz[v] + 1) * sz[v]/2;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++){
        cin >> h[i].fi;
        h[i].se = i;
        par[i] = i; sz[i] = 1;
    }
    for (int i = 1; i <= q; i ++){
        cin >> x[i].fi;
        x[i].se = i;
    }
    sort(h + 1, h + n + 1);
    sort(x + 1, x + q + 1);
    int j = 1;
    for (int i = 1; i <= q; i ++){
        while (j <= n && h[j].fi <= x[i].fi){
            ans += 1;
            if (ok[h[j].se - 1]) add(h[j].se - 1, h[j].se);
            if (ok[h[j].se + 1]) add(h[j].se + 1, h[j].se);
            ok[h[j].se] = 1;
            j ++;
        }
        res[x[i].se] = ans;
    }
    for (int i = 1; i <= q; i ++) cout << res[i] << '\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