oj.uz

답안 #556254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556254 2022-05-02T16:17:03 Z Alexandruabcde 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 337 ms 41276 KB 
#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

# 결과 실행 시간 메모리 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