Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
52618 LinkZelda 木板游戏 C++ 通过 100 319 MS 17840 KB 1487 2022-07-19 14:48:23

Tests(20/20):


#include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> #include<iostream> #include<vector> #include<queue> #include<ctime> #include<cmath> #include<queue> #include<map> #include<set> #include<unordered_map> #include<stack> #define pr pair<int,int> #define eps 1e-8 #define db double using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } const int N=1000005; pair<int,int>awa[N]; int dp[N],n; bool cmp(pr x,pr y) { if(x.second!=y.second) return x.second>y.second; return x.first<y.first; } int tr[N]; int b[N],tot; void modify(int x,int k) { for(; x<=tot; x+=x&-x) tr[x]=max(tr[x],k); } int query(int x) { int ret=0; for(; x; x-=x&-x) ret=max(ret,tr[x]); return ret; } int ans; int main() { n=read(); for(int l,r,i=1; i<=n; i++) l=read(),r=read(),awa[i]=make_pair(l,r),b[++tot]=l,b[++tot]=r; sort(awa+1,awa+n+1,cmp); sort(b+1,b+tot+1); tot=unique(b+1,b+tot+1)-(b+1); for(int i=1; i<=n; i++) awa[i].first=lower_bound(b+1,b+tot+1,awa[i].first)-b,awa[i].second=lower_bound(b+1,b+tot+1,awa[i].second)-b; for(int i=1; i<=n; i++) { dp[i]=query(awa[i].first)+1; modify(awa[i].first,dp[i]); ans=max(ans,dp[i]); } printf("%d\n",ans); return 0; }


测评信息: