제출 #1356942

#제출 시각아이디문제언어결과실행 시간메모리
1356942AzeTurk810Boat (APIO16_boat)C++20
0 / 100
569 ms2480 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#define map unordered_map

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

constexpr ll MOD = 1e9 + 7, N = 505, M = N * 4;

int _n, _m;
vector<array<ll, 2>> V;
ll ans;

long long bp(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1LL)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

inline void systemd() {
    V.resize(_n);
}

inline ll add(ll l, ll r) {
    l += r;
    while (l >= MOD) {
        l -= MOD;
    }
    return l;
}
vector<ll> compsf;
map<ll, ll> compr, rev;

int compress() {
    sort(compsf.begin(), compsf.end());
    compsf.erase(unique(compsf.begin(), compsf.end()), compsf.end());
    ll nxt = 0;
    for (const ll &v : compsf) {
        rev[nxt] = v;
        compr[v] = nxt++;
    }
    return compsf.size();
}

char solve() {
    if (!(cin >> _n))
        return 1;
    systemd();
    for (auto &[a, b] : V) {
        cin >> a >> b;
        compsf.push_back(a);
        // compsf.push_back(a - 1);
        compsf.push_back(b);
        // compsf.push_back(b - 1);
    }
    _m = compress();
    vector<vector<ll>> dp(_m, vector<ll>(_m, 0));
    for (size_t k = 0; k < _n; k++) {
        int ci = compr[V[k][0]], cj = compr[V[k][1]];
        int ai = V[k][0], bi = V[k][1];
        dp[ci][cj] = bi - ai + 1;
        for (int i = 0; i < _n; i++) {
            for (int j = i; j < _n; j++) {
                ll aj = V[i][0], bj = V[j][1];
                if (aj > bj)
                    continue;
                ll ca = compr[aj], cb = compr[bj];
                ll wj = dp[ca][cb];
                if (aj >= bi)
                    continue;
                if (bj < ai) {
                    dp[ci][cj] = add(wj, dp[ci][cj]);
                }
            }
        }
        ans = add(ans, dp[ci][cj]);
        dbg(dp[ci][cj]);
        dbg("______");
    }
    for (size_t i = 0; i < _m; i++) {
        dbg(dp[i]);
    }
    cout << ans << ln;
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…