제출 #330313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330313		jungsnow	Pilot (NOI19_pilot)	C++14	89 / 100	1014 ms	251296 KiB

pilot

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second

using namespace std;
using ll = long long;

typedef pair<int, int> ii;

const int N = 1000100;

int n, q, h[N], y[N];
int rmq[N][21], Log[N];
int p[N], s[N];

bool has[N];

ll res, query[N];

vector <ii> v, a;

int get(int l, int r) {
    int _lg = Log[r - l + 1];
    return max(rmq[l][_lg], rmq[r - (1 << _lg) + 1][_lg]);
}

void solve1() {
    for (int k = 1; k <= q; ++k) {
        int l = 0;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            while (l < i && get(l + 1, i) > y[k]) ++l;
            ans += (i - l);
        }
        cout<<ans<<'\n';
    }
}

void solve2() {
    for (int k = 1; k <= q; ++k) {
        int lo = 1, hi = n, pos = 0;
        while (lo <= hi) {
            int mi = (lo + hi) >> 1;
            if (h[mi] <= y[k]) {
                pos = mi;
                lo = mi + 1;
            } else
                hi = mi - 1;
        }
        ll ans;
        ans = 1ll * pos * (pos - 1) / 2 + pos;
        cout<<ans<<'\n';
    }
}

void solve3() {
    ll ans = 0; int l = 0;
    for (int i = 1; i <= n; ++i) {
        while (l < i && get(l + 1, i) > y[1]) ++l;
        ans += (i - l);
    }
    cout<<ans<<'\n';
}

int anc(int u) {
    return p[u] == u ? u : p[u] = anc(p[u]);
}

void merge(int u, int v) {
    u = anc(u); v = anc(v);
    if (u == v) return;
    if (s[u] < s[v]) swap(u, v);
    p[v] = u;
    res += s[u] * s[v];
    s[u] += s[v];
}

void solve() {
    sort(v.begin(), v.end()); sort(a.begin(), a.end());
    int lst = 0;
    for (int i = 0; i < q; ++i) {
        int val = v[i].x, id = v[i].y;
        int lo = lst, hi = n - 1, pos = -1;
        while (lo <= hi) {
            int mi = (lo + hi) / 2;
            if (a[mi].x <= val) {
                pos = mi;
                lo = mi + 1;
            } else {
                hi = mi - 1;
            }
        }
        for (int j = lst; j <= pos; ++j) {
            int p = a[j].y;
            if (has[p]) continue;
            has[p] = 1;
            ++res;
            if (p > 1 && has[p - 1]) merge(p, p - 1);
            if (p < n && has[p + 1]) merge(p, p + 1);
        }
        lst = max(lst, pos + 1);
        query[id] = res;
    }
    for (int i = 1; i <= q; ++i) cout << query[i] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("pilot.in", "r", stdin);
//    freopen("pilot.out", "w", stdout);
    cin >> n >> q;
    bool ok = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        a.push_back(ii(h[i], i));
        p[i] = i;
        s[i] = 1;
        rmq[i][0] = h[i];
    }
    for (int i = 2; i <= n; ++i) {
        if (h[i] <= h[i - 1]) ok = 0;
        Log[i] = Log[i / 2] + 1;
    }
    for (int j = 1; j <= 20; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
        }
    }
    for (int i = 1; i <= q; ++i) {
        cin >> y[i];
        v.push_back(ii(y[i], i));
    }
    if (max(n, q) <= 1000) solve1();
    else if (ok) solve2();
    else if (q == 1) solve3();
    else solve();
}

컴파일 시 표준 에러 (stderr) 메시지

pilot.cpp: In function 'int main()':
pilot.cpp:128:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  128 |             rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
      |                                                          ~~^~~

• 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: 0 / 11