Submission #308287

#	Time	Username	Problem	Language	Result	Execution time	Memory
308287		andreiomd	Employment (JOI16_employment)	C++11	10 / 100	5023 ms	2976 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], V[++V[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, V[++V[0]] = Queries[i].second.second;
        else
            V[++V[0]] = Queries[i].second.first;
    }

    return;
}

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

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

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

    return;
}

static inline void Solve ()
{
    for(int i = 1; i <= Q; ++i)
        if(Queries[i].first == 1)
        {
            int ans = 0;

            for(int j = 1; j <= N; ++j)
                if(A[j] >= Queries[i].second.first && A[j - 1] < Queries[i].second.first)
                    ++ans;

            cout << ans << '\n';
        }
        else
            A[Queries[i].second.first] = Queries[i].second.second;

    return;
}

int main()
{
    Read();

    Normalize();

    Solve();

    return 0;
}

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