oj.uz

답안 #1094158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094158 2024-09-28T18:43:03 Z VMaksimoski008 사다리꼴 (balkan11_trapezoid) C++17
5 / 100
 218 ms 31188 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

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

const int mod = 30013;
const int LOG = 20;
const int maxn = 1e5 + 5;

struct SegTree {
    int n;
    vector<pii> tree;

    SegTree(int _n) : n(_n), tree(4*_n, {0, 0}) {}

    pii merge(pii a, pii b) {
        if(a.first > b.first) return a;
        if(a.first < b.first) return b;
        return { a.first, (a.second + b.second) % mod };
    }

    void update(int u, int tl, int tr, int p, int v, int w) {
        if(tl == tr) {
            tree[u] = merge(tree[u], { v, w });
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v, w);
            else update(2*u+1, tm+1, tr, p, v, w);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }

    pii query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return { 0, 0 };
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int p, int v, int w) { update(1, 0, n-1, p, v, w); }
    pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};

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

    int n; cin >> n;
    vector<array<int, 4> > v(n);
    set<int> s;
    for(int i=0; i<n; i++) {
        for(int j=0; j<4; j++) cin >> v[i][j];
        for(int j=0; j<4; j++) s.insert(v[i][j]);
    }

    vector<int> comp(s.begin(), s.end());
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++)
        for(int j=0; j<4; j++) v[i][j] = lower_bound(comp.begin(), comp.end(), v[i][j]) - comp.begin();

    vector<pii> dp(n);
    SegTree tree(comp.size());
    priority_queue<pii> pq;
    for(int i=0; i<n; i++) {
        dp[i] = { 1, 1 };
        while(!pq.empty() && pq.top().first < v[i][0]) {
            tree.update(v[pq.top().second][3], dp[pq.top().second].first, dp[pq.top().second].second);
            pq.pop();
        }
        auto res = tree.query(0, v[i][2]-1);
        if(res.first) dp[i] = { res.first + 1, res.second };
        pq.push({ v[i][1], i }); 
    }

    while(!pq.empty()) {
        tree.update(v[pq.top().second][3], dp[pq.top().second].first, dp[pq.top().second].second);
        pq.pop();
    }
    auto [mx, ways] = tree.query(0, comp.size() - 1);
    cout << mx << " " << ways << '\n';
    return 0;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 3 ms 1096 KB Output isn't correct
6 Incorrect 4 ms 1372 KB Output isn't correct
7 Incorrect 5 ms 1048 KB Output isn't correct
8 Incorrect 8 ms 1884 KB Output isn't correct
9 Incorrect 16 ms 3932 KB Output isn't correct
10 Incorrect 23 ms 4484 KB Output isn't correct
11 Incorrect 42 ms 8784 KB Output isn't correct
12 Incorrect 100 ms 17624 KB Output isn't correct
13 Incorrect 145 ms 20436 KB Output isn't correct
14 Incorrect 145 ms 25248 KB Output isn't correct
15 Incorrect 163 ms 22464 KB Output isn't correct
16 Incorrect 184 ms 23844 KB Output isn't correct
17 Incorrect 200 ms 28364 KB Output isn't correct
18 Incorrect 118 ms 18388 KB Output isn't correct
19 Incorrect 192 ms 29884 KB Output isn't correct
20 Incorrect 218 ms 31188 KB Output isn't correct