oj.uz

Submission #308294

# Submission time Handle Problem Language Result Execution time Memory
308294 2020-09-30T20:40:08 Z andreiomd Employment (JOI16_employment) C++11
30 / 100
 356 ms 24312 KB 
#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(pos > 1 && 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(pos > 1 && 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 19 ms 2040 KB Output is correct
5 Correct 41 ms 3568 KB Output is correct
6 Correct 71 ms 6392 KB Output is correct
7 Correct 111 ms 11256 KB Output is correct
8 Correct 143 ms 12024 KB Output is correct
9 Correct 259 ms 23032 KB Output is correct
10 Correct 244 ms 21624 KB Output is correct
11 Correct 308 ms 23672 KB Output is correct
12 Correct 346 ms 24184 KB Output is correct
13 Correct 356 ms 24056 KB Output is correct
14 Correct 330 ms 24056 KB Output is correct
15 Correct 343 ms 24060 KB Output is correct
16 Correct 348 ms 24184 KB Output is correct
17 Correct 353 ms 24184 KB Output is correct
18 Correct 350 ms 24312 KB Output is correct
19 Correct 342 ms 24312 KB Output is correct
20 Correct 343 ms 24312 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -