Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
52375 _ 木板游戏 C++ 通过 100 582 MS 13392 KB 1361 2022-07-19 12:03:38

Tests(20/20):


#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; }


测评信息: