Submission #556254

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556254	2022-05-02T16:17:03 Z	Alexandruabcde	trapezoid (balkan11_trapezoid)	C++14	100 / 100	337 ms	41276 KB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, bool> PIB;
constexpr int NMAX = 1e5 + 5;
constexpr int MOD = 30013;

struct Node {
    int Max;
    int fr;
};

Node Comb (Node st, Node dr) {
    Node ans;
    if (st.Max > dr.Max) {
        ans.Max = st.Max;
        ans.fr = st.fr;
    }
    else if (st.Max < dr.Max) {
        ans.Max = dr.Max;
        ans.fr = dr.fr;
    }
    else {
        ans.Max = st.Max;
        ans.fr = (st.fr + dr.fr) % MOD;
    }

    return ans;
}

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

    void Update (int nod, int a, int b, int pos, Node value) {
        if (a == b) {
            arb[nod] = value;
            return;
        }

        int mij = (a + b) / 2;
        if (pos <= mij) Update(2*nod, a, mij, pos, value);
        else Update(2*nod+1, mij+1, b, pos, value);

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

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

        int mij = (a + b) / 2;

        if (qa <= mij && mij < qb) return Comb(Query(2*nod, a, mij, qa, qb), Query(2*nod+1, mij+1, b, qa, qb));
        else if (qa <= mij) return Query(2*nod, a, mij, qa, qb);
        else return Query(2*nod+1, mij+1, b, qa, qb);
    }

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

    void Update (int pos, Node value) {
        Update(1, 1, sz, pos, value);
    }

    int Length (int C) {
        if (C == 1) return 0;

        return Query(1, 1, sz, 1, C-1).Max;
    }

    int Count (int C) {
        if (C == 1) return 0;

        return Query(1, 1, sz, 1, C-1).fr;
    }
};

SegmentTree SGT;

struct Trapezoid {
    int a, b;
    int c, d;
};

Trapezoid T[NMAX];
int N;

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

    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> T[i].a >> T[i].b >> T[i].c >> T[i].d;
}

vector <PIB> Event[2*NMAX];
int cnt_ab, cnt_cd;

void Precompute () {
    map <int, int> mp_ab, mp_cd;

    for (int i = 1; i <= N; ++ i ) {
        mp_ab[T[i].a] = 1;
        mp_ab[T[i].b] = 1;

        mp_cd[T[i].c] = 1;
        mp_cd[T[i].d] = 1;
    }

    for (auto &it : mp_ab)
        it.second = ++cnt_ab;
    for (auto &it : mp_cd)
        it.second = ++cnt_cd;

    for (int i = 1; i <= N; ++ i ) {
        T[i].a = mp_ab[T[i].a];
        T[i].b = mp_ab[T[i].b];
        T[i].c = mp_cd[T[i].c];
        T[i].d = mp_cd[T[i].d];
    }

    for (int i = 1; i <= N; ++ i ) {
        Event[T[i].a].push_back({i, 1});
        Event[T[i].b].push_back({i, 0});
    }
    SGT.Init(cnt_cd);
}

int Best_Lg[NMAX];
int Cnt[NMAX];

void Solve () {
    for (int i = 1; i <= cnt_ab; ++ i ) {
        for (auto it : Event[i]) {
            int ind = it.first;

            if (it.second) {
                ///Query
                Best_Lg[ind] = SGT.Length(T[ind].c) + 1;
                Cnt[ind] = SGT.Count(T[ind].c);

                if (Best_Lg[ind] == 1) Cnt[ind] = 1;
            }
            else {
                SGT.Update(T[ind].d, {Best_Lg[ind], Cnt[ind]});
            }
        }
    }

    int ans_Max = 0, ans_cnt = 0;
    for (int i = 1; i <= N; ++ i ) {
        if (Best_Lg[i] > ans_Max) {
            ans_Max = Best_Lg[i];
            ans_cnt = Cnt[i];
        }
        else if (Best_Lg[i] == ans_Max) {
            ans_cnt = (ans_cnt + Cnt[i]) % MOD;
        }
    }

    cout << ans_Max << " " << ans_cnt << '\n';
}

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

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	5 ms	5204 KB	Output is correct
4	Correct	4 ms	5332 KB	Output is correct
5	Correct	7 ms	5716 KB	Output is correct
6	Correct	9 ms	6072 KB	Output is correct
7	Correct	10 ms	6496 KB	Output is correct
8	Correct	14 ms	6812 KB	Output is correct
9	Correct	25 ms	8576 KB	Output is correct
10	Correct	46 ms	12224 KB	Output is correct
11	Correct	59 ms	14116 KB	Output is correct
12	Correct	148 ms	23148 KB	Output is correct
13	Correct	181 ms	26804 KB	Output is correct
14	Correct	211 ms	30532 KB	Output is correct
15	Correct	269 ms	32268 KB	Output is correct
16	Correct	282 ms	33984 KB	Output is correct
17	Correct	309 ms	35980 KB	Output is correct
18	Correct	235 ms	37656 KB	Output is correct
19	Correct	286 ms	39548 KB	Output is correct
20	Correct	337 ms	41276 KB	Output is correct