Submission #320935

#	Time	Username	Problem	Language	Result	Execution time	Memory
320935		lohacho	Employment (JOI16_employment)	C++14	100 / 100	292 ms	14048 KiB

employment

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int N, M;
int a[NS];
int q[NS][3];
vector<int> srt;
struct fenwick{
    vector < int > fenw;
    int N;
    fenwick(){}
    fenwick(int n):N(n){
        fenw.resize(N);
    }
    void push(int x, int val){
        for(int i = x; i < N; i += (i & -i)){
            fenw[i] += val;
        }
    }
    int get(int x){
        int rv = 0;
        for(int i = x; i; i -= (i & -i)){
            rv += fenw[i];
        }
        return rv;
    }
}fen(NS * 2), lfen(NS * 2);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for(int i = 1; i <= N; ++i){
        cin >> a[i];
        srt.push_back(a[i]);
    }
    for(int i = 1; i <= M; ++i){
        cin >> q[i][0] >> q[i][1];
        if(q[i][0] - 1){
            cin >> q[i][2];
            srt.push_back(q[i][2]);
        }
        else{
            srt.push_back(q[i][1]);
        }
    }
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    for(int i = 1; i <= N; ++i){
        a[i] = lower_bound(srt.begin(), srt.end(), a[i]) - srt.begin() + 1;
        fen.push(a[i], 1);
        if(i > 1){
            lfen.push(min(a[i], a[i - 1]), 1);
        }
    }
    for(int i = 1; i <= M; ++i){
        q[i][q[i][0]] = lower_bound(srt.begin(), srt.end(), q[i][q[i][0]]) - srt.begin() + 1;
        if(q[i][0] == 1){
            cout << fen.get(NS * 2 - 1) - fen.get(q[i][1] - 1) - (lfen.get(NS * 2 - 1) - lfen.get(q[i][1] - 1)) << '\n';
        }
        else{
            fen.push(a[q[i][1]], -1);
            if(q[i][1] > 1){
                lfen.push(min(a[q[i][1]], a[q[i][1] - 1]), -1);
            }
            if(q[i][1] < N){
                lfen.push(min(a[q[i][1]], a[q[i][1] + 1]), -1);
            }
            a[q[i][1]] = q[i][2];
            fen.push(a[q[i][1]], 1);
            if(q[i][1] > 1){
                lfen.push(min(a[q[i][1]], a[q[i][1] - 1]), 1);
            }
            if(q[i][1] < N){
                lfen.push(min(a[q[i][1]], a[q[i][1] + 1]), 1);
            }
        }
    }
    return 0;
}

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