Submission #284353

#	Time	Username	Problem	Language	Result	Execution time	Memory
284353		Alexa2001	Employment (JOI16_employment)	C++17	100 / 100	217 ms	12148 KiB

employment

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 4e5 + 5;

int n, q, m;
int tip[Nmax/2], val[Nmax/2], p[Nmax/2], a[Nmax/2];

vector<int> all;



class AIB
{
    int ub(int x) { return (x&(-x)); }
    int a[Nmax];

public:
    void upd(int x, int y, int add)
    {
        for(; y; y-=ub(y)) a[y] += add;
        for(--x; x; x-=ub(x)) a[x] -= add;
    }

    int query(int x)
    {
        int ans = 0;
        for(; x<=m; x+=ub(x)) ans += a[x];
        return ans;
    }


} aib;




void cb(int &x)
{
    x = lower_bound(all.begin(), all.end(), x) - all.begin() + 1;
}

void init()
{
    int i;
    vector<int> s(m+2);

    for(i=1; i<=n; ++i)
        if(a[i] > a[i+1])
            aib.upd(a[i+1] + 1, a[i], +1);
}

void update(int pos, int val)
{
    if(pos-1 && a[pos-1] > a[pos])
        aib.upd(a[pos] + 1, a[pos-1], -1);

    if(a[pos] > a[pos+1])
        aib.upd(a[pos+1] + 1, a[pos], -1);

    a[pos] = val;

    if(pos-1 && a[pos-1] > a[pos])
        aib.upd(a[pos] + 1, a[pos-1], +1);

    if(a[pos] > a[pos+1])
        aib.upd(a[pos+1] + 1, a[pos], +1);
}

int main()
{
   // freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> q;

    int i;
    for(i=1; i<=n; ++i)
    {
        cin >> a[i];
        all.push_back(a[i]);
    }

    for(i=1; i<=q; ++i)
    {
        cin >> tip[i] >> p[i];
        if(tip[i] == 2)
        {
            cin >> val[i];
            all.push_back(val[i]);
        }
    }

    all.push_back(0);

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

    m = all.size() + 1;

    for(i=1; i<=n+1; ++i)
        cb(a[i]);

    for(i=1; i<=q; ++i)
        if(tip[i] == 1) cb(p[i]);
            else cb(val[i]);

    init();

    for(i=1; i<=q; ++i)
        if(tip[i] == 1)
            cout << aib.query(p[i]) << '\n';
        else update(p[i], val[i]);

    return 0;
}

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