Submission #996053

#	Time	Username	Problem	Language	Result	Execution time	Memory
996053		gmroh06	Employment (JOI16_employment)	C++14	100 / 100	241 ms	29060 KiB

employment

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void fastio() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

class Fenwick {
private:
    vector<ll> tree;
    ll n;

public:
    Fenwick(ll x) {
        n = x;
        tree.resize(x + 1);
    }

    void add(ll idx, ll val) {
        for (ll x = idx + 1; x <= n; x += x & -x) {
            tree[x] += val;
        }
    }

    ll sum(ll idx) {
        ll ret = 0;

        for (ll x = idx; x > 0; x &= x - 1) {
            ret += tree[x];
        }

        return ret;
    }
};

int main() {
    fastio();

    ll n, m;

    cin >> n >> m;

    vector<ll> arr(n + 1);

    for (ll i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    vector<tuple<ll, ll, ll>> query(m);
    vector<ll> val = arr;

    for (auto& [t, a, b] : query) {
        cin >> t;

        if (t == 1) {
            cin >> a;
            val.emplace_back(a);
        } else {
            cin >> a >> b;
            val.emplace_back(b);
        }
    }

    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    for (auto& x : arr) {
        x = lower_bound(val.begin(), val.end(), x) - val.begin();
    }

    for (auto& [t, a, b] : query) {
        if (t == 1) {
            a = lower_bound(val.begin(), val.end(), a) - val.begin();
        } else {
            b = lower_bound(val.begin(), val.end(), b) - val.begin();
        }
    }

    const ll MAX = n + m << 1;

    Fenwick tree(MAX | 1), min_tree(MAX | 1);

    auto add = [&](ll idx, ll val) {
        tree.add(arr[idx], val);
        min_tree.add(min(arr[idx - 1], arr[idx]), val);
    };

    for (ll i = 1; i <= n; i++) {
        add(i, 1);
    }

    for (auto& [t, a, b] : query) {
        if (t == 1) {
            cout << (tree.sum(MAX) - tree.sum(a)) - (min_tree.sum(MAX) - min_tree.sum(a)) << '\n';
        } else {
            add(a, -1);
            if (a != n) add(a + 1, -1);

            arr[a] = b;

            add(a, 1);
            if (a != n) add(a + 1, 1);
        }
    }

    return 0;
}

Compilation message (stderr)

employment.cpp: In function 'int main()':
employment.cpp:56:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto& [t, a, b] : query) {
      |                ^
employment.cpp:75:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for (auto& [t, a, b] : query) {
      |                ^
employment.cpp:83:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   83 |     const ll MAX = n + m << 1;
      |                    ~~^~~
employment.cpp:96:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for (auto& [t, a, b] : query) {
      |                ^

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