제출 #1321233

#제출 시각아이디문제언어결과실행 시간메모리
1321233viobowtrapezoid (balkan11_trapezoid)C++17
50 / 100
1097 ms7064 KiB
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define re exit(0);
#define FOR(i, a, b)   for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b)  for(int i = (a), _b = (b); i >= _b; i--)
#define LOOP(a)        for(int i = 0, _a = (a); i < _a; i++)
#define left (id<<1)
#define right (id<<1|1)
#define _lower(v, x) lower_bound(v.begin(), v.end(), x) - v.begin() + 1

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

template<typename T> void chkmin(T &x, T y) {if (y < x) x = y;}
template<typename T> void chkmax(T &x, T y) {if (y > x) x = y;}

const int mod = 30013;
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int _pow(int a, int b) {
   int ans = 1;
   while (b) {
   if (b % 2 == 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b /= 2;
   }
   return ans;
}

//--------------------------------------------------------------------------------------------------------------------------------------

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

    Trapezoid() {
        a = b = c = d = 0;
    }

    bool operator< (const Trapezoid &other) const {
        if (b != other.b) {
            return b < other.b;
        }
        return c < other.c;
    }

};

const int maxn = 2e5;
Trapezoid tra[maxn + 5];
int n;

int dp[maxn + 5], ways[maxn + 5];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //#define name "mooo"
    //if (fopen(name".inp", "r")) {
    //     freopen(name".inp", "r", stdin);
    //     freopen(name".out", "w", stdout);
    //}
    
    cin >> n; 
    for (int i = 1; i <= n; i++)
        cin >> tra[i].a >> tra[i].b >> tra[i].c >> tra[i].d;
        
    sort(tra + 1, tra + n + 1);

    
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (tra[j].b < tra[i].a && tra[j].d < tra[i].c)
                chkmax(dp[i], dp[j] + 1);
        }
    }

    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (tra[j].b < tra[i].a && tra[j].d < tra[i].c && dp[i] == dp[j] + 1) {
                add(ways[i], ways[j]);
            }
        }
    }

    int max_set = *max_element(dp, dp + n + 1);
    int num_ways = 0;

    for (int i = 1; i <= n; i++)
        if (dp[i] == max_set)
            add(num_ways, ways[i]);

    cout << max_set << ' ' << num_ways << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...