oj.uz

Submission #880508

# Submission time Handle Problem Language Result Execution time Memory
880508 2023-11-29T14:50:56 Z kh0i trapezoid (balkan11_trapezoid) C++17
100 / 100
 101 ms 21428 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;   

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const ll mod = 30013;

struct Trapezoid{
    int a, b, c, d;
    bool operator < (const Trapezoid &o){ return a < o.a; }
};

pll combine(const pll &A, const pll &B){
    pll res;
    res.F = max(A.F, B.F);
    if(A.F == B.F) res.S = (A.S + B.S) % mod;
    else if(A.F < B.F) res.S = B.S;
    else res.S = A.S;
    return res;
}

struct SegTri{
    vector<pll> st;
    int n;

    void init(int _n){
        n = _n;
        st.resize(4 * n + 6, {0, 0});
    } 

    void _update(int id, int l, int r, int pos, pll val){
        if(l == r){
            st[id] = combine(st[id], val);
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid)
            _update(2 * id, l, mid, pos, val);
        else
            _update(2 * id + 1, mid + 1, r, pos, val);
        st[id] = combine(st[2 * id], st[2 * id + 1]);
    }

    pll _get(int id, int l, int r, int tl, int tr){
        if(l > tr or tl > r)
            return {0, 0};
        if(tl <= l and r <= tr)
            return st[id];
        int mid = (l + r) / 2;
        return combine(_get(2 * id, l, mid, tl, tr), _get(2 * id + 1, mid + 1, r, tl, tr));
    }

    void update(int pos, pll val){
        _update(1, 1, n, pos, val);
    }

    pll get(int l, int r){
        if(l > r)
            return {0, 0};
        return _get(1, 1, n, l, r);
    }
} dak;

const int N = 1e5 + 3;

int n;
vector<Trapezoid> tr;
vector<pair<Trapezoid, int>> tr_b;
vector<int> xx = {0};
pll f[N];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        tr.push_back({a, b, c, d});
        xx.push_back(c);
        xx.push_back(d);
    }

    sort(all(xx));
    xx.resize(unique(all(xx)) - xx.begin());
    sort(all(tr));
    for(auto &[a, b, c, d] : tr){
        c = lower_bound(all(xx), c) - xx.begin() + 1;
        d = lower_bound(all(xx), d) - xx.begin() + 1;
    }

    for(int i = 0; i < sz(tr); ++i)
        tr_b.push_back({tr[i], i});

    sort(all(tr_b), [](const pair<Trapezoid, int> &A, const pair<Trapezoid, int> &B) -> bool {
        return A.F.b < B.F.b;
    });

    dak.init(sz(xx) + 2);
    dak.update(1, {0, 1});

    int cur = 0;
    for(int i = 0; i < sz(tr); ++i){
        debug(tr[i].a, tr[i].b, tr[i].c, tr[i].d);
        while(cur < i and tr_b[cur].F.b < tr[i].a){
            dak.update(tr_b[cur].F.d, f[tr_b[cur].S]);
            ++cur;
        };
        f[i] = dak.get(1, tr[i].c - 1);
        f[i].F += 1;
        debug(i, f[i]);
    }

    pll res = {0, 1};
    for(int i = 0; i < sz(tr); ++i)
        res = combine(res, f[i]);
    cout << res.F << ' ' << res.S << '\n';
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 5 ms 1628 KB Output is correct
9 Correct 9 ms 2580 KB Output is correct
10 Correct 17 ms 4944 KB Output is correct
11 Correct 27 ms 5824 KB Output is correct
12 Correct 50 ms 11256 KB Output is correct
13 Correct 58 ms 13364 KB Output is correct
14 Correct 71 ms 16816 KB Output is correct
15 Correct 77 ms 16612 KB Output is correct
16 Correct 83 ms 17584 KB Output is correct
17 Correct 93 ms 19120 KB Output is correct
18 Correct 78 ms 19760 KB Output is correct
19 Correct 92 ms 20696 KB Output is correct
20 Correct 101 ms 21428 KB Output is correct