Submission #478050

#	Time	Username	Problem	Language	Result	Execution time	Memory
478050		chungdinh	Pilot (NOI19_pilot)	C++14	89 / 100	1056 ms	39044 KiB

pilot

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ll long long
#define ii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define r first
#define c second

#define all(x) x.begin(), x.end()

ostream& operator << (ostream& os, pair<int, int> a) {
    return os << a.first << " : " << a.second;
}

#define endl '\n'
#define db(val) "["#val" = "<<(val)<<"] "
#define cntbit(x) __builtin_popcount(x)

const int N = 1e6 + 5;
const int iINF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1e18;

int n, q;
int h[N];

ii a[N];
int id[N];

ll res[N];
bool below[N];

ll f(int x) {return (ll)x*(x + 1)/2;}

int p[N];
int sz[N];
int find(int u) {
    if (u == p[u]) return u;
    return p[u] = find(p[u]);
}
void sss(int u, int v, ll &subres) {
    u = find(u); v = find(v);
    subres -= f(sz[u]) + f(sz[v]);

    p[u] = v;
    sz[v] += sz[u];
    subres += f(sz[v]);
}


int main() {
    #ifdef CHUNGDINH
    freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);
    #endif
    memset(below, false, sizeof below);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        id[i] = i;
        cin >> h[i];
        p[i] = i; sz[i] = 1;
    }
    sort(id + 1, id + n + 1, [](int x, int y){return h[x] < h[y];});

    for (int i = 1; i <= q; i++) {
        cin >> a[i].first; a[i].second = i;
    }
    sort(a + 1, a + q + 1);

    // case n == 1;

    ll subres = 0;
    int ss = 1;
    for (int i = 1; i <= q; i++) {
        while (ss <= n && h[id[ss]] <= a[i].first) {

            subres++;
            int pl = id[ss];

            below[pl] = true;
            if (pl <= n - 1 && below[pl + 1]) {
                sss(pl, pl + 1, subres);
            }
            if (pl >= 2 && below[pl - 1]) sss(pl, pl - 1, subres);

            ss++;
        }

        res[a[i].second] = subres;
    }
    //for (int i = 1; i <= n; i++) cout << id[i] << " ";

    for (int i = 1; i <= q; i++) cout << res[i] << endl;
}

/*
Array bounds *
long long vs int
Garbage value
Sometimes, VNOI views "arrays out of bounds" as "wrong answer"
*/

• 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