Submission #556254

#	Time	Username	Problem	Language	Result	Execution time	Memory
556254		Alexandruabcde	trapezoid (balkan11_trapezoid)	C++14	100 / 100	337 ms	41276 KiB

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 / 100