제출 #522278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522278		andreiomd	Employment (JOI16_employment)	C++11	100 / 100	596 ms	29276 KiB

employment

#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 4e5 + 2;

class SegmentTree
{
    long long Aint[4 * NMAX], Lazy[4 * NMAX];
private:
    void Propag(int nod, int a, int b)
    {
        if(a == b)
            return;
        if(Lazy[nod] == 0)
            return;

        int mid = (a + b) >> 1;

        Aint[2 * nod] += 1LL * Lazy[nod] * (mid - a + 1);
        Aint[2 * nod + 1] += 1LL * Lazy[nod] * (b - mid);

        Lazy[2 * nod] += Lazy[nod];
        Lazy[2 * nod + 1] += Lazy[nod];

        Lazy[nod] = 0;
        return;
    }
public:
    void Update(int node, int a, int b, int ua, int ub, int val)
    {
        if(ua > ub)
            return;
        if(ua <= a && b <= ub) {
            Aint[node] += 1LL * val * (b - a + 1);
            Lazy[node] += val;
            return;
        }

        Propag(node, a, b);
        int mid = (a + b) >> 1;

        if(ua <= mid)
            Update(2 * node, a, mid, ua, ub, val);
        if(mid < ub)
            Update(2 * node + 1, mid + 1, b, ua, ub, val);

        Aint[node] = Aint[2 * node] + Aint[2 * node + 1];
        return;
    }

    long long Query(int node, int a, int b, int qa, int qb)
    {
        if(qa <= a && b <= qb) {
            return Aint[node];
        }

        Propag(node, a, b);
        int mid = (a + b) >> 1;

        long long s1 = 0, s2 = 0;
        if(qa <= mid)
            s1 = Query(2 * node, a, mid, qa, qb);
        if(mid < qb)
            s2 = Query(2 * node + 1, mid + 1, b, qa, qb);

        return s1 + s2;
    }
} seg;

struct qry
{
    int tip;
    int x;
    int pos;
    int val;
};

int N, Q;
int v[NMAX], norm[NMAX], n2[NMAX];
qry q[NMAX];

void Normalise()
{
    sort(norm + 1, norm + norm[0] + 1);

    for(int i = 1; i <= norm[0]; i++)
        if(norm[i] != norm[i - 1] || i == 1)
            n2[++n2[0]] = norm[i];

    for(int i = 1; i <= N; i++)
        v[i] = (int)(lower_bound(n2 + 1, n2 + n2[0] + 1, v[i]) - n2);

    for(int i = 1; i <= Q; i++) {
        if(q[i].tip == 1)
            q[i].x = (int)(lower_bound(n2 + 1, n2 + n2[0] + 1, q[i].x) - n2);
        else q[i].val = (int)(lower_bound(n2 + 1, n2 + n2[0] + 1, q[i].val) - n2);
    }

}

void Read()
{
    cin >> N >> Q;

    for(int i = 1; i <= N; i++)
        cin >> v[i], norm[++norm[0]] = v[i];
    for(int i = 1; i <= Q; i++){
        cin >> q[i].tip;
        if(q[i].tip == 1)
            cin >> q[i].x, norm[++norm[0]] = q[i].x;
        else {
            cin >> q[i].pos >> q[i].val;
            norm[++norm[0]] = q[i].val;
        }
    }

}

int main()
{
    Read();
    Normalise();

    for(int i = 1; i <= N; i++) {
        if(v[i - 1] < v[i])
            seg.Update(1, 1, n2[0], v[i - 1] + 1, v[i], +1);
    }

    for(int i = 1; i <= Q; i++) {
        if(q[i].tip == 1) {
            cout << seg.Query(1, 1, n2[0], q[i].x, q[i].x) << '\n';
        }
        else {
            int p = q[i].pos;

            if(v[p - 1] < v[p])
                seg.Update(1, 1, n2[0], v[p - 1] + 1, v[p], -1);
            if(p != N && v[p] < v[p + 1])
                seg.Update(1, 1, n2[0], v[p] + 1, v[p + 1], -1);

            v[p] = q[i].val;

            if(v[p - 1] < v[p])
                seg.Update(1, 1, n2[0], v[p - 1] + 1, v[p], +1);
            if(p != N && v[p] < v[p + 1])
                seg.Update(1, 1, n2[0], v[p] + 1, v[p + 1], +1);
        }
    }
    return 0;
}

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