oj.uz

Submission #743744

# Submission time Handle Problem Language Result Execution time Memory
743744 2023-05-17T21:45:51 Z dioji trapezoid (balkan11_trapezoid) C++17
50 / 100
 500 ms 11836 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7392 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7400 KB Output is correct
5 Correct 10 ms 7500 KB Output is correct
6 Correct 18 ms 7400 KB Output is correct
7 Correct 20 ms 7560 KB Output is correct
8 Correct 34 ms 7508 KB Output is correct
9 Correct 167 ms 7772 KB Output is correct
10 Correct 422 ms 8360 KB Output is correct
11 Execution timed out 1067 ms 8524 KB Time limit exceeded
12 Execution timed out 1073 ms 9824 KB Time limit exceeded
13 Execution timed out 1037 ms 10208 KB Time limit exceeded
14 Execution timed out 1035 ms 10760 KB Time limit exceeded
15 Execution timed out 1082 ms 10760 KB Time limit exceeded
16 Execution timed out 1060 ms 11184 KB Time limit exceeded
17 Execution timed out 1075 ms 11252 KB Time limit exceeded
18 Execution timed out 1073 ms 11492 KB Time limit exceeded
19 Execution timed out 1067 ms 11764 KB Time limit exceeded
20 Execution timed out 1070 ms 11836 KB Time limit exceeded