fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<vector>
  12. #include<bitset>
  13. #include<functional>
  14. #define x first
  15. #define y second
  16. #define mp make_pair
  17. #define pb push_back
  18. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  19. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  20. using namespace std;
  21.  
  22. typedef long long LL;
  23. typedef double ld;
  24.  
  25. const int MAX=1000000+10;
  26.  
  27. int K,n;
  28. int x1[MAX],y1[MAX],x2[MAX],y2[MAX];
  29.  
  30. int tot;
  31. pair<int,int> node[MAX];
  32. int mm[MAX],dp[MAX],dp1[MAX],add[MAX];
  33.  
  34. int cmp(const pair<int,int>& a,const pair<int,int>& b)
  35. {
  36.     return (LL)a.x*b.y<(LL)a.y*b.x;
  37. }
  38.  
  39. void merge(int& a,int& b)
  40. {
  41.     int g=__gcd(a,b);
  42.     a/=g;
  43.     b/=g;
  44. }
  45.  
  46. int main()
  47. {
  48. #ifndef ONLINE_JUDGE
  49. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  50. #endif
  51.     int i;
  52.     scanf("%d%d",&K,&n);
  53.     REP(i,1,n)
  54.     {
  55.         scanf("%d%d%d%d",x1+i,y1+i,x2+i,y2+i);
  56.         merge(x1[i],y1[i]);
  57.         merge(x2[i],y2[i]);
  58.         node[++tot]=mp(x1[i],y1[i]);
  59.         node[++tot]=mp(x2[i],y2[i]);
  60.     }
  61.     sort(node+1,node+tot+1,cmp);
  62.     tot=unique(node+1,node+tot+1)-node-1;
  63.  
  64.     REP(i,1,tot)
  65.         mm[i]=i+1;
  66.     REP(i,1,n)
  67.     {
  68.         int L=lower_bound(node+1,node+tot+1,mp(x1[i],y1[i]),cmp)-node;
  69.         int R=lower_bound(node+1,node+tot+1,mp(x2[i],y2[i]),cmp)-node;
  70.         if(L>R)
  71.             swap(L,R);
  72.         mm[R]=min(mm[R],L);
  73.         add[L]++;
  74.         add[R+1]--;
  75.     }
  76.     for(i=tot-1;i>=1;--i)
  77.         mm[i]=min(mm[i+1],mm[i]);
  78.     for(i=1;i<=tot;++i)
  79.         add[i]+=add[i-1];
  80.     dp[0]=0;
  81.     for(int j=1;j<=K;++j)
  82.     {
  83.         for(i=1;i<=tot;++i)
  84.             dp1[i]=dp[mm[i]-1] + add[i];
  85.         for(i=1;i<=tot;++i)
  86.         {
  87.             dp[i]=max(dp[i], dp1[i] );
  88.             if(dp[i]<dp[i-1])
  89.                 dp[i]=dp[i-1];
  90.         }
  91.     }
  92.     printf("%d\n",dp[tot]);
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 42368KB
comments (?)
stdin
copy 
3 6
1 2 2 4
3 1 5 1
3 2 2 3
3 3 3 4
2 2 2 2
6 1 3 5
stdout
copy 
5
https://ideone.com/ftIiJe
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!