oj.uz

Submission #880501

# Submission time Handle Problem Language Result Execution time Memory
880501 2023-11-29T14:43:34 Z kh0i trapezoid (balkan11_trapezoid) C++17
5 / 100
 92 ms 17088 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<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;
    }

    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[cur].b < tr[i].a){
            debug(tr[cur].d, f[cur]);
            dak.update(tr[cur].d, f[cur]);
            ++cur;
        };
        f[i] = dak.get(1, tr[i].c - 1);
        f[i].F += 1;
        debug(i, f[i]);
    }

    pll res = {0, 0};
    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:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Incorrect 2 ms 604 KB Output isn't correct
6 Incorrect 2 ms 1112 KB Output isn't correct
7 Incorrect 3 ms 1116 KB Output isn't correct
8 Incorrect 4 ms 1372 KB Output isn't correct
9 Incorrect 8 ms 2264 KB Output isn't correct
10 Incorrect 15 ms 3796 KB Output isn't correct
11 Incorrect 21 ms 4564 KB Output isn't correct
12 Incorrect 44 ms 8644 KB Output isn't correct
13 Incorrect 52 ms 10300 KB Output isn't correct
14 Incorrect 63 ms 11956 KB Output isn't correct
15 Incorrect 69 ms 12980 KB Output isn't correct
16 Incorrect 72 ms 13824 KB Output isn't correct
17 Incorrect 78 ms 14440 KB Output isn't correct
18 Incorrect 70 ms 15316 KB Output isn't correct
19 Incorrect 82 ms 16168 KB Output isn't correct
20 Incorrect 92 ms 17088 KB Output isn't correct