oj.uz

Submission #985230

# Submission time Handle Problem Language Result Execution time Memory
985230 2024-05-17T13:22:32 Z LOLOLO trapezoid (balkan11_trapezoid) C++17
100 / 100
 265 ms 39936 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 5 ms 11356 KB Output is correct
6 Correct 7 ms 11612 KB Output is correct
7 Correct 7 ms 11500 KB Output is correct
8 Correct 10 ms 11868 KB Output is correct
9 Correct 19 ms 13720 KB Output is correct
10 Correct 29 ms 15068 KB Output is correct
11 Correct 46 ms 18384 KB Output is correct
12 Correct 105 ms 26368 KB Output is correct
13 Correct 149 ms 29184 KB Output is correct
14 Correct 170 ms 33272 KB Output is correct
15 Correct 206 ms 32108 KB Output is correct
16 Correct 218 ms 33788 KB Output is correct
17 Correct 240 ms 36748 KB Output is correct
18 Correct 143 ms 31632 KB Output is correct
19 Correct 225 ms 38652 KB Output is correct
20 Correct 265 ms 39936 KB Output is correct