Submission #577362

#	Time	Username	Problem	Language	Result	Execution time	Memory
577362		Alexandruabcde	Osumnjičeni (COCI21_osumnjiceni)	C++14	60 / 110	1010 ms	50148 KiB

Main

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;

class SegmentTree {
private:
    vector <int> arb;
    vector <int> lazy;
    int sz;

    void Add (int nod, int value) {
        arb[nod] += value;
        lazy[nod] += value;
    }

    void Propag (int nod, int a, int b) {
        if (lazy[nod] == 0) return;

        if (a == b) return;

        for (int i = 2 * nod; i <= 2 * nod + 1; ++ i )
            Add(i, lazy[nod]);
        lazy[nod] = 0;
    }

    void Update (int nod, int a, int b, int ua, int ub, int val) {
        if (ua <= a && b <= ub) {
            Add(nod, val);
            return;
        }

        Propag(nod, a, b);
        int mij = (a + b) / 2;

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

        arb[nod] = max(arb[2*nod], arb[2*nod+1]);
    }

    int Query (int nod, int a, int b, int qa, int qb) {
        if (qa <= a && b <= qb) return arb[nod];

        Propag(nod, a, b);
        int mij = (a + b) / 2;
        int left = 0, right = 0;

        if (qa <= mij) left = Query(2*nod, a, mij, qa, qb);
        if (mij < qb) right = Query(2*nod+1, mij+1, b, qa, qb);

        return max(left, right);
    }

public:
    void Init (int Size) {
        sz = Size;
        arb.resize(4*(sz+1));
        lazy.resize(4*(sz+1));

        for (int i = 1; i <= 4 * sz; ++ i )
            arb[i] = lazy[i] = 0;
    }

    void Update (int val_st, int val_dr, int value) {
        Update(1, 1, sz, val_st, val_dr, value);
    }

    int FindWorst (int st, int dr) {
        return Query(1, 1, sz, st, dr);
    }
};

int N, Q;
int L[NMAX], R[NMAX];
int vf = 0;

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> L[i] >> R[i];
}

void Normalize () {
    map <int, int> mp;

    for (int i = 1; i <= N; ++ i )
        mp[L[i]] = mp[R[i]] = 1;

    for (auto &it : mp)
        it.second = ++vf;

    for (int i = 1; i <= N; ++ i ) {
        L[i] = mp[L[i]];
        R[i] = mp[R[i]];
    }
}

int urm[20][NMAX];
int LastPower;

void Precompute () {
    Normalize();
    SegmentTree SGT;
    SGT.Init(vf);

    int dr = 0;
    for (int i = 1; i <= N; ++ i ) {
        if (dr < i) {
            ++ dr;
            SGT.Update(L[i], R[i], 1);
        }

        while (dr < N && SGT.FindWorst(L[dr+1], R[dr+1]) == 0) {
            SGT.Update(L[dr+1], R[dr+1], 1);
            ++ dr;
        }

        SGT.Update(L[i], R[i], -1);
        urm[0][i] = dr+1;
    }

    for (int lg = 1; (1<<lg) <= N; ++ lg ) {
        LastPower = lg;
        for (int i = 1; i + (1<<lg) - 1 <= N; ++ i )
            urm[lg][i] = urm[lg-1][urm[lg-1][i]];
    }
}

int Ask (int st, int dr) {
    int ans = 1;
    for (int i = LastPower; i >= 0; -- i ) {
        if (urm[i][st] <= dr && urm[i][st] != 0) {
            st = urm[i][st];
            ans += (1<<i);
        }
    }

    return ans;
}

void Solve () {
    cin >> Q;
    for (int i = 1; i <= Q; ++ i ) {
        int st, dr;
        cin >> st >> dr;

        cout << Ask(st, dr) << '\n';
    }
}

int main () {
    Read();
    Precompute();
    Solve();

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 50