oj.uz

답안 #567313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567313 2022-05-23T10:26:57 Z hgmhc 사다리꼴 (balkan11_trapezoid) C++17
2 / 100
 132 ms 5976 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);
    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
2.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 340 KB Partially correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 3 ms 340 KB Output isn't correct
6 Incorrect 3 ms 468 KB Output isn't correct
7 Incorrect 5 ms 468 KB Output isn't correct
8 Incorrect 6 ms 596 KB Output isn't correct
9 Incorrect 10 ms 980 KB Output isn't correct
10 Incorrect 21 ms 1648 KB Output isn't correct
11 Incorrect 33 ms 1896 KB Output isn't correct
12 Incorrect 68 ms 3512 KB Output isn't correct
13 Incorrect 69 ms 3316 KB Output isn't correct
14 Incorrect 75 ms 4788 KB Output isn't correct
15 Incorrect 104 ms 4872 KB Output isn't correct
16 Incorrect 105 ms 5076 KB Output isn't correct
17 Incorrect 110 ms 5372 KB Output isn't correct
18 Incorrect 91 ms 5424 KB Output isn't correct
19 Incorrect 118 ms 4956 KB Output isn't correct
20 Incorrect 132 ms 5976 KB Output isn't correct