Submission #308295

#	Time	Username	Problem	Language	Result	Execution time	Memory
308295		andreiomd	Employment (JOI16_employment)	C++11	100 / 100	529 ms	28664 KiB

employment

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair < int, int > PII;
typedef pair < int, PII > Type;

const int NMAX = 2e5 + 1, QMAX = 2e5 + 1;

int N, Q, A[NMAX];
Type Queries[QMAX];

int B[(NMAX + QMAX)], V[(NMAX + QMAX)];

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Q;

    for(int i = 1; i <= N; ++i)
        cin >> A[i], B[++B[0]] = A[i];

    for(int i = 1; i <= Q; ++i)
    {
        cin >> Queries[i].first >> Queries[i].second.first;

        if(Queries[i].first == 2)
            cin >> Queries[i].second.second, B[++B[0]] = Queries[i].second.second;
        else
            B[++B[0]] = Queries[i].second.first;
    }

    return;
}

static inline int Find (int Val)
{
    return (int)(lower_bound(V + 1, V + V[0] + 1, Val) - V);
}

static inline void Replace ()
{
    for(int i = 1; i <= N; ++i)
        A[i] = Find(A[i]);

    for(int i = 1; i <= Q; ++i)
        if(Queries[i].first == 1)
            Queries[i].second.first = Find(Queries[i].second.first);
        else
            Queries[i].second.second = Find(Queries[i].second.second);

    return;
}

static inline void Normalize ()
{
    sort(B + 1, B + B[0] + 1);

    V[++V[0]] = B[1];

    for(int i = 2; i <= B[0]; ++i)
        if(B[i] != B[i - 1])
            V[++V[0]] = B[i];

    Replace();

    return;
}

class SegmentTree
{
    static const int NMAX = (4e5 + 1);
    long long A[(NMAX << 2)], Lazy[(NMAX << 2)];

private:
    inline void Go (int Node, int a, int b)
    {
        if(a == b)
            return;

        if(Lazy[Node] == 0)
            return;

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

        A[(Node << 1)] += 1LL * Lazy[Node] * (Mid - a + 1), Lazy[(Node << 1)] += 1LL * Lazy[Node];
        A[((Node << 1) + 1)] += 1LL * Lazy[Node] * (b - Mid), Lazy[((Node << 1) + 1)] += 1LL * Lazy[Node];

        Lazy[Node] = 0;

        return;
    }

public:
    inline void Update (int Node, int a, int b, int ua, int ub, int Val)
    {
        if(ua <= a && b <= ub)
        {
            Lazy[Node] += 1LL * Val;
            A[Node] += 1LL * Val * (b - a + 1);

            return;
        }

        Go(Node, a, b);

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

        if(ua <= Mid)
            Update((Node << 1), a, Mid, ua, ub, Val);

        if(ub > Mid)
            Update(((Node << 1) + 1), Mid + 1, b, ua, ub, Val);

        A[Node] = A[(Node << 1)] + A[((Node << 1) + 1)];

        return;
    }

    inline long long Query (int Node, int a, int b, int qa, int qb)
    {
        if(qa <= a && b <= qb)
            return A[Node];

        Go(Node, a, b);

        int Mid = ((a + b) >> 1);
        long long p_Left = 0, p_Right = 0;

        if(qa <= Mid)
            p_Left = Query((Node << 1), a, Mid, qa, qb);

        if(qb > Mid)
            p_Right = Query(((Node << 1) + 1), Mid + 1, b, qa, qb);

        return (p_Left + p_Right);
    }
} AINT;

static inline void Initialize ()
{
    for(int i = 1; i <= N; ++i)
        if(A[i] > A[i - 1])
            AINT.Update(1, 1, V[0], A[i - 1] + 1, A[i], 1);

    return;
}

static inline void Solve ()
{
    Initialize();

    for(int i = 1; i <= Q; ++i)
        if(Queries[i].first == 1)
            cout << AINT.Query(1, 1, V[0], Queries[i].second.first, Queries[i].second.first) << '\n';
        else
        {
            int pos = Queries[i].second.first, X = Queries[i].second.second;

            if(A[pos] > A[pos - 1])
                AINT.Update(1, 1, V[0], A[pos - 1] + 1, A[pos], -1);

            if(pos < N && A[pos] < A[pos + 1])
                AINT.Update(1, 1, V[0], A[pos] + 1, A[pos + 1], -1);

            A[pos] = X;

            if(A[pos] > A[pos - 1])
                AINT.Update(1, 1, V[0], A[pos - 1] + 1, A[pos], 1);

            if(pos < N && A[pos] < A[pos + 1])
                AINT.Update(1, 1, V[0], A[pos] + 1, A[pos + 1], 1);
        }

    return;
}

int main()
{
    Read();

    Normalize();

    Solve();

    return 0;
}

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