Submission #24777

#	Time	Username	Problem	Language	Result	Execution time	Memory
24777		chpipis	trapezoid (balkan11_trapezoid)	C++11	40 / 100	129 ms	9380 KiB

trapezoid

#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 (stderr)

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 / 100