Submission #1356960

#TimeUsernameProblemLanguageResultExecution timeMemory
1356960AzeTurk810Boat (APIO16_boat)C++20
9 / 100
7 ms572 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <array>
#include <cassert>
#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();
}

ll mult(ll l, ll r) {
    return (l * r) % MOD;
}

struct BIT {
    int _n;
    vector<ll> T;
    BIT(int n) : _n(n), T(_n + 1, 0) {
    }

    void upd(int i, ll x) {
        i ++;
        while (i <= _n) {
            dbg(i);
            T[i] = add(T[i], x);
            i += i & -i;
        }
    }

    ll sum(int l, int r) {
        if (l != 1) {
            return sum(1, r) - sum(1, l - 1);
        }
        r++;
        ll res = 0;
        while (r > 0) {
            res = add(res, T[r]);
            r -= (r) & (-r);
        }
        return res;
    }
};

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();
    BIT t(_m + 2);
    for (int i = 0; i < _n; i++) {
        int l = compr[V[i][0]], r = compr[V[i][1]];

        vector<pair<int, ll>> updates;
        for (int x = l; x <= r; x++) {
            ll ways = 1;
            if (x > 0) {
                ways = add(ways, t.sum(1, x - 1));
            }
            updates.push_back({x, ways});
        }
        for (auto &[pos, val] : updates) {
            t.upd(pos, val);
        }
    }
    cout << t.sum(1, _m - 1) << 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
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...