Submission #330312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
330312	2020-11-24T18:11:27 Z	jungsnow	Pilot (NOI19_pilot)	C++14	Compilation error	0 ms	0 KB

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();
}

Compilation message

pilot.cpp:1:1: error: 'include' does not name a type
    1 | include<bits/stdc++.h>
      | ^~~~~~~
pilot.cpp:9:9: error: 'pair' does not name a type
    9 | typedef pair<int, int> ii;
      |         ^~~~
pilot.cpp:21:1: error: 'vector' does not name a type
   21 | vector <ii> v, a;
      | ^~~~~~
pilot.cpp: In function 'long long int get(long long int, long long int)':
pilot.cpp:25:12: error: 'max' was not declared in this scope
   25 |     return max(rmq[l][_lg], rmq[r - (1 << _lg) + 1][_lg]);
      |            ^~~
pilot.cpp: In function 'void solve1()':
pilot.cpp:36:9: error: 'cout' was not declared in this scope
   36 |         cout<<ans<<'\n';
      |         ^~~~
pilot.cpp: In function 'void solve2()':
pilot.cpp:53:9: error: 'cout' was not declared in this scope
   53 |         cout<<ans<<'\n';
      |         ^~~~
pilot.cpp: In function 'void solve3()':
pilot.cpp:63:5: error: 'cout' was not declared in this scope
   63 |     cout<<ans<<'\n';
      |     ^~~~
pilot.cpp: In function 'void merge(long long int, long long int)':
pilot.cpp:73:22: error: 'swap' was not declared in this scope
   73 |     if (s[u] < s[v]) swap(u, v);
      |                      ^~~~
pilot.cpp: In function 'void solve()':
pilot.cpp:80:10: error: 'v' was not declared in this scope
   80 |     sort(v.begin(), v.end()); sort(a.begin(), a.end());
      |          ^
pilot.cpp:80:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   80 |     sort(v.begin(), v.end()); sort(a.begin(), a.end());
      |     ^~~~
      |     short
pilot.cpp:80:36: error: 'a' was not declared in this scope
   80 |     sort(v.begin(), v.end()); sort(a.begin(), a.end());
      |                                    ^
pilot.cpp:102:15: error: 'max' was not declared in this scope
  102 |         lst = max(lst, pos + 1);
      |               ^~~
pilot.cpp:103:15: error: 'id' was not declared in this scope; did you mean 'i'?
  103 |         query[id] = res;
      |               ^~
      |               i
pilot.cpp:105:34: error: 'cout' was not declared in this scope
  105 |     for (int i = 1; i <= q; ++i) cout << query[i] << '\n';
      |                                  ^~~~
pilot.cpp: In function 'int main()':
pilot.cpp:109:5: error: 'ios' has not been declared
  109 |     ios::sync_with_stdio(0);
      |     ^~~
pilot.cpp:110:5: error: 'cin' was not declared in this scope
  110 |     cin.tie(0); cout.tie(0);
      |     ^~~
pilot.cpp:110:17: error: 'cout' was not declared in this scope
  110 |     cin.tie(0); cout.tie(0);
      |                 ^~~~
pilot.cpp:117:9: error: 'a' was not declared in this scope
  117 |         a.push_back(ii(h[i], i));
      |         ^
pilot.cpp:117:21: error: 'ii' was not declared in this scope; did you mean 'i'?
  117 |         a.push_back(ii(h[i], i));
      |                     ^~
      |                     i
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]);
      |                                                          ~~^~~
pilot.cpp:128:25: error: 'max' was not declared in this scope
  128 |             rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
      |                         ^~~
pilot.cpp:133:9: error: 'v' was not declared in this scope
  133 |         v.push_back(ii(y[i], i));
      |         ^
pilot.cpp:133:21: error: 'ii' was not declared in this scope; did you mean 'i'?
  133 |         v.push_back(ii(y[i], i));
      |                     ^~
      |                     i
pilot.cpp:135:9: error: 'max' was not declared in this scope
  135 |     if (max(n, q) <= 1000) solve1();
      |         ^~~