oj.uz

Submission #24777

# Submission time Handle Problem Language Result Execution time Memory
24777 2017-06-13T19:00:36 Z chpipis trapezoid (balkan11_trapezoid) C++11
40 / 100
 129 ms 9380 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 1e5 + 5;

struct side {
    int l, r, idx;
    bool right_end;
};

inline bool comp(const side &lhs, const side &rhs) {
    if (lhs.l == rhs.l)
        return lhs.right_end < rhs.right_end;
    return lhs.l < rhs.l;
}

vector<side> seg;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int dp[MAXN], cnt[MAXN];
vi cc;

int bit_max[MAXN * 2];

#define lsone(s) (s & (-s))

void add_max(int b, int val) {
    while (b < MAXN * 2) {
        bit_max[b] = max(bit_max[b], val);
        b += lsone(b);
    }
}

int ask_max(int b) {
    int res = 0;
    while (b > 0) {
        res = max(res, bit_max[b]);
        b -= lsone(b);
    }
    return res;
}

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    cc.pb(0);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
        cc.pb(c[i]);
        cc.pb(d[i]);
    }
    sort(all(cc));
    cc.resize(unique(all(cc)) - cc.begin());

    seg.reserve(2 * n + 1);

    for (int i = 1; i <= n; i++) {
        c[i] = lower_bound(all(cc), c[i]) - cc.begin();
        d[i] = lower_bound(all(cc), d[i]) - cc.begin();
        seg.pb((side){a[i], c[i], i, false});
        seg.pb((side){b[i], d[i], i, true});
    }
    seg.pb((side){(int)2e9, 2 * n + 5, n + 1, false});

    sort(all(seg), comp);

    for (auto it : seg) {
        if (it.right_end) {
            add_max(it.r, dp[it.idx]);
        } else {
            dp[it.idx] = ask_max(it.r - 1) + 1;
            //cnt[it.idx] = freq[dp[it.idx] - 1];
        }
    }
    dp[n + 1]--;

    printf("%d %d\n", dp[n + 1], cnt[n + 1]);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:94:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
trapezoid.cpp:97:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
                                                         ^

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 5148 KB Partially correct
2 Partially correct 0 ms 5148 KB Partially correct
3 Partially correct 0 ms 5148 KB Partially correct
4 Partially correct 0 ms 5148 KB Partially correct
5 Partially correct 0 ms 5320 KB Partially correct
6 Partially correct 3 ms 5288 KB Partially correct
7 Partially correct 3 ms 5288 KB Partially correct
8 Partially correct 3 ms 5448 KB Partially correct
9 Partially correct 6 ms 5672 KB Partially correct
10 Partially correct 19 ms 6112 KB Partially correct
11 Partially correct 23 ms 6268 KB Partially correct
12 Partially correct 73 ms 7304 KB Partially correct
13 Partially correct 83 ms 7616 KB Partially correct
14 Partially correct 83 ms 8440 KB Partially correct
15 Partially correct 86 ms 8596 KB Partially correct
16 Partially correct 99 ms 8756 KB Partially correct
17 Partially correct 99 ms 8912 KB Partially correct
18 Partially correct 129 ms 9068 KB Partially correct
19 Partially correct 123 ms 9224 KB Partially correct
20 Partially correct 123 ms 9380 KB Partially correct