Submission #743744

#	Time	Username	Problem	Language	Result	Execution time	Memory
743744		dioji	trapezoid (balkan11_trapezoid)	C++17	50 / 100	1082 ms	11836 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll st, ll dr) {
    assert(st <= dr);
    return st + rng() % (dr - st + 1);
}

namespace Modular {
    template<int MOD>
    struct ModInt {
        long long v;
        ModInt(long long _v = 0) {v = (-MOD < _v && _v < MOD) ? _v : _v % MOD; if (v < 0) v += MOD;}
        ModInt& operator += (const ModInt &other) {v += other.v; if (v >= MOD) v -= MOD; return *this;}
        ModInt& operator -= (const ModInt &other) {v -= other.v; if (v < 0) v += MOD; return *this;}
        ModInt& operator *= (const ModInt &other) {v = v * other.v % MOD; return *this;}
        ModInt& operator /= (const ModInt &other) {return *this *= inverse(other);}
        bool operator == (const ModInt &other) const {return v == other.v;}
        bool operator != (const ModInt &other) const {return v != other.v;}
        friend ModInt operator + (ModInt a, const ModInt &b) {return a += b;}
        friend ModInt operator - (ModInt a, const ModInt &b) {return a -= b;}
        friend ModInt operator * (ModInt a, const ModInt &b) {return a *= b;}
        friend ModInt operator / (ModInt a, const ModInt &b) {return a /= b;}
        friend ModInt operator - (const ModInt &a) {return 0 - a;}
        friend ModInt power(ModInt a, long long b) {ModInt ret(1); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
        friend ModInt inverse(ModInt a) {return power(a, MOD - 2);}
        friend ostream& operator << (ostream &os, const ModInt &m) {return os << m.v;}
    };
    
    const int N = 2e5 + 5; // CHANGE !!!
    const int MOD = 30013; // CHANGE !!!
    typedef ModInt<MOD> Mint;

    Mint power(long long _a, long long b) {Mint ret(1), a(_a); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}

    Mint fact[N], inv[N];
    
    void init() {
        fact[0] = 1;
        for (int i = 1; i < N; i++)
            fact[i] = fact[i - 1] * i;
        inv[N - 1] = inverse(fact[N - 1]);
        for (int i = N - 2; i >= 0; i--)
            inv[i] = inv[i + 1] * (i + 1);
    }

    Mint choose(int n, int k) {
        return ((n < k || k < 0) ? 0 : fact[n] * inv[k] * inv[n - k]);
    }
}

using Modular::Mint;
using Modular::power;
using Modular::choose;

const int MOD = 1e9 + 7;
///////////////////////////////////////////////////////////
const int N = 5e5 + 10;

struct lol {
    int l, r, L, R;
    bool operator <(const lol &other) const {
        return r < other.r;
    }
};

int n;
lol a[N];
Mint dp[N];
int mx[N];

void solve(int test, istream &cin, ostream &cout) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r >> a[i].L >> a[i].R;
    }
    sort(a + 1, a + n + 1);
    mx[1] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        int best = 0;
        for (int j = 1; j < i; j++) {
            if (a[j].r < a[i].l && a[j].R < a[i].L) {
                best = max(best, mx[j]);
            }
        }
        mx[i] = best + 1;
        // cout << "( " << a[i].l << ' ' << a[i].r << ' ' << a[i].L << ' ' << a[i].R << ")\n";
        for (int j = 1; j < i; j++) {
            if (a[j].r < a[i].l && a[j].R < a[i].L && mx[j] == best) {
                dp[i] += dp[j];
            }
        }
        if (best == 0) {
            dp[i] = 1;
        }
        // cout << mx[i] << " -> " << dp[i] << '\n';
    }

    int best = *max_element(mx + 1, mx + n + 1);
    Mint ans = 0;
    for (int i = 1; i <= n; i++) {
        if (mx[i] == best) {
            // cout << i << ' ' << dp[i].v << '\n';
            ans += dp[i];
        }
    }

    cout << best << ' ' << ans << '\n';
}

int main() {
    // ifstream cin("tst.in");
    // ofstream cout("tst.out");
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    bool multiTest = false;

    int t;    
    if (multiTest) {
        cin >> t;
    } else {
        t = 1;
    }

    for (int test = 1; test <= t; test++) {
        solve(test, cin, cout);
    }

    return 0;
}

• Subtask 1: 50 / 100