Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
52375 | _ | 木板游戏 | C++ | 通过 | 100 | 582 MS | 13392 KB | 1361 | 2022-07-19 12:03:38 |
#include <bits/stdc++.h> using namespace std; const int MXN = 500005; int N, ns[MXN], nn, mxv[MXN << 2]; struct Board { int l, r; } bds[MXN]; inline bool operator<(Board a, Board b) { return a.l == b.l ? a.r > b.r : a.l < b.l; } inline int ls(int p) { return p << 1; } inline int rs(int p) { return p << 1 | 1; } int query(int p, int l, int r, int tl, int tr) { if (l >= tl && r <= tr) return mxv[p]; if (l >= tr || r <= tl) return 0; int mid((l + r) >> 1); return max(query(ls(p), l, mid, tl, tr), query(rs(p), mid, r, tl, tr)); } void change(int p, int l, int r, int t, int v) { if (r - l == 1) { mxv[p] = max(mxv[p], v); return; } int mid((l + r) >> 1); if (t >= mid) change(rs(p), mid, r, t, v); else change(ls(p), l, mid, t, v); mxv[p] = max(mxv[ls(p)], mxv[rs(p)]); } int main() { cin >> N; for (int i(0); i != N; ++i) { cin >> bds[i].l >> bds[i].r; ns[nn++] = bds[i].r; } sort(bds, bds + N); sort(ns, ns + nn); nn = unique(ns, ns + nn) - ns; for (int i(0); i != N; ++i) { bds[i].r = lower_bound(ns, ns + nn, bds[i].r) - ns; // cout << bds[i].l << ' ' << bds[i].r << endl; } int ans(0); for (int i(0); i != N; ++i) { int mxp(query(1, 0, nn, bds[i].r, nn)); ans = max(ans, mxp + 1); change(1, 0, nn, bds[i].r, mxp + 1); } cout << ans << endl; return 0; }