제출 #933169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933169		JooDdae	Employment (JOI16_employment)	C++17	100 / 100	201 ms	18112 KiB

employment

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, a[200200], t[1001001], N;
vector<int> X;
vector<array<int, 2>> query;

void update(int b, int x) {
    while(b <= N) t[b] += x, b += b & -b;
}

int find(int b) {
    int re = 0;
    while(b) re += t[b], b -= b & -b;
    return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) X.push_back(a[i]), X.push_back(a[i]+1);
    for(int i=1;i<=m;i++) {
        int q; cin >> q;
        if(q == 1) {
            int x; cin >> x;
            X.push_back(x);
            query.push_back({0, x});
        } else {
            int x, y; cin >> x >> y;
            X.push_back(y), X.push_back(y);
            query.push_back({x, y});
        }
    }
    sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());
    N = X.size();
    for(int i=1;i<=n;i++) a[i] = lower_bound(X.begin(), X.end(), a[i]) - X.begin() + 1;
    for(int i=1;i<n;i++) if(a[i] != a[i+1]) update(min(a[i], a[i+1])+1, 1), update(max(a[i], a[i+1])+1, -1);

    for(auto [x, y] : query) {
        y = lower_bound(X.begin(), X.end(), y) - X.begin() + 1;
        if(x) {
            for(int i=max(1,x-1);i<=min(n-1,x);i++) if(a[i] != a[i+1]) {
                update(min(a[i], a[i+1])+1, -1), update(max(a[i], a[i+1])+1, 1);
            }
            a[x] = y;
            for(int i=max(1,x-1);i<=min(n-1,x);i++) if(a[i] != a[i+1]) {
                update(min(a[i], a[i+1])+1, 1), update(max(a[i], a[i+1])+1, -1);
            }
        } else {
            int k = find(y);

            if(a[1] >= y) cout << (k+2)/2 << "\n";
            else cout << (k+1)/2 << "\n";
        }
    }
}

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