Submission #985230

#	Time	Username	Problem	Language	Result	Execution time	Memory
985230		LOLOLO	trapezoid (balkan11_trapezoid)	C++17	100 / 100	265 ms	39936 KiB

trapezoid

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 4e5 + 10;
int mod = 30013;
vector <pair <int, pair <int, int>>> add[N];

void process(pair <int, int> &a, pair <int, int> b) {
    if (a.f < b.f) {
        a = b;
    } else if (a.f == b.f) {
        a.s += b.s;
        if (a.s >= mod)
            a.s -= mod;
    }
}

pair <int, int> f[N];

void upd(int i, pair <int, int> A) {
    for (; i < N; i += i & (-i))
        process(f[i], A);
}

pair <int, int> get(int i) {
    pair <int, int> A = {0, 0};
    for (; i; i -= i & (-i))
        process(A, f[i]);

    return A;
}

void solve() {
    int n;
    cin >> n;

    vector < vector <int>> trap;
    upd(1, {0, 1});

    map <int, int> mp;
    int timer = 1;
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        trap.pb({a, b, c, d});
        mp[a], mp[b], mp[c], mp[d];
    }

    for (auto &x : mp)
        x.s = ++timer;

    for (auto &x : trap) {
        for (int j = 0; j < 4; j++)
            x[j] = mp[x[j]];
    }

    sort(all(trap));
    int j = 0;

    for (int i = 1; i <= timer; i++) {
        while (j < sz(trap) && trap[j][0] <= i) {
            pair <int, int> pt = get(trap[j][2] - 1);
            pt.f++;
            add[trap[j][1]].pb({trap[j][3], pt});
            j++;
        }

        for (auto x : add[i]) {
            upd(x.f, x.s);
        }
    }

    pair <int, int> ans = get(N - 1);
    cout << ans.f << ' ' << ans.s << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}  

• Subtask 1: 100 / 100