Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
52529 | seanlsy | 木板游戏 | C++ | 解答错误 | 0 | 18 MS | 1800 KB | 814 | 2022-07-19 12:38:46 |
#include <bits/stdc++.h> using namespace std; int n,longest; pair<int,int> f[100005],d[100005]; #define l first #define r second inline int read() { int x=0; bool f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-')f=0; ch=getchar(); } while(ch<='9'&&ch>='0') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return f?x:-x; } int main() { n=read(),f[0].r=1e9; for(int i=1; i<=n; i++) { d[i].l=read(),d[i].r=read(); if(d[i].l>=f[longest].l&&d[i].r<=f[longest].r) f[++longest]=d[i]; else { int l=0,r=longest; while(l<r-1) { int mid=l+r>>1; if(d[i].l>=f[mid].l&&d[i].r<=f[mid].r) l=mid; else r=mid; } f[l+1]=d[i]; } } printf("%d\n",longest); return 0; }