Submission #1220207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220207		duckindog	Employment (JOI16_employment)	C++20	100 / 100	138 ms	6360 KiB

employment

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, q;
int a[N];
struct { 
    int type, x, y;
} query[N];

vector<int> allValue;
namespace BIT { 
    int bit[N << 1];
    inline void upd(int i, int x) { 
        for (; i; i -= i & -i) bit[i] += x;
    }
    inline int que(int i) { 
        int ret = 0;
        for (; i <= (int)allValue.size(); i += i & -i) ret += bit[i];
        return ret;
    }
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= q; ++i) { 
        auto& [type, x, y] = query[i];
        cin >> type;
        if (type == 1) cin >> x;
        else cin >> x >> y;
    }

    allValue.assign(a + 1, a + n + 1);
    for (int i = 1; i <= q; ++i) { 
        if (query[i].type == 2) allValue.push_back(query[i].y);
    }
    sort(allValue.begin(), allValue.end());
    allValue.erase(unique(allValue.begin(), allValue.end()), allValue.end());

    for (int i = 1; i <= n; ++i) { 
        a[i] = upper_bound(allValue.begin(), allValue.end(), a[i]) - allValue.begin();
    }

    auto modify = [&](int p, int x) { 
        BIT::upd(a[p], x);
        if (p > 1 && a[p - 1] >= a[p]) BIT::upd(a[p], -x);
        if (p < n && a[p + 1] > a[p]) BIT::upd(a[p], -x);
    };
    for (int i = 1; i <= n; ++i) modify(i, 1);

    for (int i = 1; i <= q; ++i) { 
        auto [type, x, y] = query[i];

        if (type == 1) { 
            x = lower_bound(allValue.begin(), allValue.end(), x) - allValue.begin() + 1;
            cout << BIT::que(x) << "\n";
        } else { 
            y = upper_bound(allValue.begin(), allValue.end(), y) - allValue.begin();

            modify(x, -1);
            if (x > 1) modify(x - 1, -1);
            if (x < n) modify(x + 1, -1);
            a[x] = y;
            modify(x, 1);
            if (x > 1) modify(x - 1, 1);
            if (x < n) modify(x + 1, 1);
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60