oj.uz

Submission #880499

# Submission time Handle Problem Language Result Execution time Memory
880499 2023-11-29T14:41:19 Z kh0i trapezoid (balkan11_trapezoid) C++17
5 / 100
 97 ms 19784 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 = 2023;

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 468 KB Output is correct
2 Incorrect 1 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 856 KB Output isn't correct
6 Incorrect 3 ms 1116 KB Output isn't correct
7 Incorrect 3 ms 1116 KB Output isn't correct
8 Incorrect 5 ms 1372 KB Output isn't correct
9 Incorrect 9 ms 2264 KB Output isn't correct
10 Incorrect 19 ms 4308 KB Output isn't correct
11 Incorrect 21 ms 5400 KB Output isn't correct
12 Incorrect 45 ms 10140 KB Output isn't correct
13 Incorrect 53 ms 11988 KB Output isn't correct
14 Incorrect 63 ms 14008 KB Output isn't correct
15 Incorrect 71 ms 14948 KB Output isn't correct
16 Incorrect 75 ms 15796 KB Output isn't correct
17 Incorrect 79 ms 16780 KB Output isn't correct
18 Incorrect 74 ms 17764 KB Output isn't correct
19 Incorrect 83 ms 18808 KB Output isn't correct
20 Incorrect 97 ms 19784 KB Output isn't correct