oj.uz

답안 #567341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567341 2022-05-23T10:42:22 Z hgmhc 사다리꼴 (balkan11_trapezoid) C++17
40 / 100
 126 ms 7860 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define fi first
#define se second
#define Mup(x,y) x = max(x,y)

const int N = 1e5+3;
int n;
priority_queue<pair<ii,int>,vector<pair<ii,int>>,less<>> pq;
struct segment_tree {
    int t[2*N], c[2*N];
    void update(int k, int v) {
        for (t[k += N] = v; (k /= 2) >= 1;) {
            // if (t[2*k] < t[2*k+1]) c[k] = c[2*k+1];
            // else if (t[2*k] > t[2*k+1]) c[k] = c[2*k];
            // else c[k] = c[2*k]+c[2*k+1];
            t[k] = max(t[2*k],t[2*k+1]);
        }
    }
    int query(int a, int b) {
        int r = 0;
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) r = max(r,t[a]);
            if (~b&1) r = max(r,t[b]);
        }
        return r;
    }
} ds;
pair<ii,ii> t[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    vector<int> xs, ys;
    rep(i,1,n) {
        cin >> t[i].fi.fi >> t[i].se.fi;
        xs.push_back(t[i].fi.fi), xs.push_back(t[i].se.fi);
        cin >> t[i].fi.se >> t[i].se.se;
        ys.push_back(t[i].fi.se), ys.push_back(t[i].se.se);
    }
    sort(all(xs)), xs.erase(unique(all(xs)),end(xs));
    sort(all(ys)), ys.erase(unique(all(ys)),end(ys));
    rep(i,1,n) {
        t[i].fi.fi = lower_bound(all(xs),t[i].fi.fi)-begin(xs);
        t[i].fi.se = lower_bound(all(ys),t[i].fi.se)-begin(ys);
        t[i].se.fi = lower_bound(all(xs),t[i].se.fi)-begin(xs);
        t[i].se.se = lower_bound(all(ys),t[i].se.se)-begin(ys);
    }
    sort(t+1,t+n+1);
    if (n <= 5000) {
        int lis[N] {0,}, cnt[N] {0,};
        int ans1 = 0, ans2 = 0;
        rep(i,1,n) {
            lis[i] = 1, cnt[i] = 1;
            rep(j,1,n-1) {
                if (t[j].se.fi < t[i].fi.fi and t[j].se.se < t[i].fi.se) {
                    if (lis[i] < lis[j]+1) {
                        lis[i] = lis[j]+1;
                        cnt[i] = cnt[j];
                    } else if (lis[i] == lis[j]+1)
                        cnt[i] = (cnt[i]+cnt[j])%30013;
                }
            }
            ans1 = max(ans1, lis[i]);
        }
        // rep(i,1,n) debug(lis[i],cnt[i]);
        rep(i,1,n) if (ans1 == lis[i])
            ans2 = (ans2+cnt[i])%30013;
        cout << ans1 << ' ' << ans2;
    } else {
        int answer = 0;
        rep(i,1,n) {
            auto [p1,p2] = t[i];
            while (not empty(pq) and pq.top().fi.fi < p1.fi) {
                ds.update(pq.top().fi.se,pq.top().se);
                pq.pop();
            }
            int v = ds.query(1,p1.se)+1;
            answer = max(answer,v);
            pq.push({p2,v});
        }
        cout << answer << ' ' << 1;
    }
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 6 ms 1168 KB Output is correct
5 Correct 13 ms 1240 KB Output is correct
6 Correct 26 ms 1304 KB Output is correct
7 Correct 67 ms 1236 KB Output is correct
8 Correct 55 ms 1392 KB Output is correct
9 Incorrect 14 ms 1932 KB Output isn't correct
10 Incorrect 25 ms 2868 KB Output isn't correct
11 Incorrect 32 ms 3216 KB Output isn't correct
12 Incorrect 75 ms 4816 KB Output isn't correct
13 Incorrect 77 ms 4628 KB Output isn't correct
14 Incorrect 92 ms 6204 KB Output isn't correct
15 Incorrect 104 ms 6332 KB Output isn't correct
16 Incorrect 101 ms 6716 KB Output isn't correct
17 Incorrect 122 ms 6968 KB Output isn't correct
18 Incorrect 99 ms 7240 KB Output isn't correct
19 Incorrect 126 ms 6756 KB Output isn't correct
20 Incorrect 125 ms 7860 KB Output isn't correct