fork download
copy 
  1. #include<map>  
  2. #include<set>  
  3. #include<stack>  
  4. #include<cmath>  
  5. #include<ctime>  
  6. #include<vector>  
  7. #include<string>  
  8. #include<bitset>  
  9. #include<cstdio>  
  10. #include<cstdlib>  
  11. #include<cstring>  
  12. #include<climits>  
  13. #include<complex>  
  14. #include<iostream>  
  15. #include<algorithm>  
  16. using namespace std;
  17. const int  inf=2e9+9;
  18. const int bit=31;
  19. struct segment
  20. {
  21.     int a,b,id;
  22.     bool operator <(const segment &temp)const
  23.     {
  24.         return a<temp.a;
  25.     }
  26. };
  27. segment sg[11111],nsg[11111];
  28. struct pp
  29. {
  30.     int id,vl;
  31.     bool operator <(const pp &temp)const
  32.     {
  33.         return vl<temp.vl;
  34.     }
  35. };
  36. pp list[11111];
  37. int n,T,ch,ls[22222],cnt_ls;
  38. int dp[11111];
  39. int vec[10001][(10000/bit)+1],ii[10001][(10000)/bit+1],ni[(10000)/bit+1],nvec[(10000/bit)+1],on[10000/bit+1];
  40. int one[10001][(10000/bit)+1];
  41. map<int,int>hs;
  42. vector<int>adj[11111];
  43. int lowbit(int x)
  44. {
  45.     return x&-x;
  46. }
  47. int upper_bound(int left,int right,int x)
  48. {
  49.     int mid;
  50.     while(left<=right)
  51.     {
  52.         mid=(left+right)>>1;
  53.         if(ls[mid]<x)
  54.            left=mid+1;
  55.         else
  56.            right=mid-1;
  57.     }
  58.     return left;
  59. }
  60. void insert(int id,int flag,int vec[],int ii[],int one[])
  61. {
  62. 	int i,j,s,p,q,ix=id/bit;
  63. 	if(flag>0)
  64. 	   vec[ix]|=(1<<(id%bit));
  65.     else
  66.        vec[ix]^=(1<<(id%bit));
  67.     one[ix]+=flag;
  68. 	int sum=0;
  69. 	ii[ix]=inf;
  70. 	for(i=0;i<bit;i++)
  71.     {
  72.     	if(vec[ix]&(1<<i))
  73.     	{
  74. 	    	sum++;
  75. 	    	if(ii[ix]>list[ix*bit+i].vl-sum*T)
  76. 	    	   ii[ix]=list[ix*bit+i].vl-sum*T;
  77. 	    }
  78.     }
  79. }
  80. int find_min(int vec[],int ii[],int one[])
  81. {
  82. 	int i,ret=inf,sum=0;
  83. 	for(i=0;i<=(n-1)/bit;i++)
  84. 	{
  85. 		if(ret>ii[i]-sum*T)
  86. 		   ret=ii[i]-sum*T;
  87.         sum+=one[i];
  88. 	}
  89. 	return ret;
  90. }
  91. int main()
  92. {
  93.     scanf("%d%d",&n,&T);
  94.     int i,j,s,p,q,sum,nn,id,nowt,ip,ie,k,mb,nf;
  95.     int  mi;
  96.     for(i=0;i<n;i++)
  97.         scanf("%d%d",&sg[i].a,&sg[i].b);
  98.     sort(sg,sg+n);
  99.     cnt_ls=0;
  100.     for(i=0;i<n;i++)
  101.     {
  102.         list[i].vl=sg[i].b;
  103.         list[i].id=i;
  104.         ls[cnt_ls++]=sg[i].a;
  105.     }
  106.     sort(ls,ls+cnt_ls);
  107.     nn=0;
  108.     for(i=0;i<cnt_ls;i++)
  109.     {
  110.         if(nn==0||ls[nn-1]<ls[i])
  111.            ls[nn++]=ls[i];
  112.     }
  113.     cnt_ls=nn;
  114.     hs.clear();
  115.     for(i=0;i<cnt_ls;i++)
  116.        hs[ls[i]]=i;
  117.     for(i=0;i<cnt_ls;i++)
  118.         adj[i].clear();
  119.     for(i=0;i<n;i++)
  120.     {
  121.         id=hs[sg[i].a];
  122.         adj[id].push_back(i);
  123.     }
  124.     sort(list,list+n);
  125.     for(i=0;i<n;i++)
  126.        sg[list[i].id].id=i;
  127.     i=0;
  128.     for(i=0;i<=cnt_ls;i++)
  129.        dp[i]=-inf;
  130.     dp[0]=inf;
  131.     memset(vec[0],0,sizeof(vec[0]));
  132.     memset(one[0],0,sizeof(one[0]));
  133.     for(i=0;i<=(n-1)/bit;i++)
  134.         ii[0][i]=inf;
  135.     int nxt=0;
  136.     for(i=0;i<cnt_ls;)
  137.     {
  138.         if(dp[i]<ls[i])
  139.         {
  140.            dp[i]=-inf;
  141.            i++;
  142.            continue;
  143.         }
  144.         for(j=0;j<=(n-1)/bit;j++)
  145.         {
  146.             nvec[j]=vec[i][j];
  147.             ni[j]=ii[i][j];
  148.             on[j]=one[i][j];
  149.         }
  150.         for(j=0;j<adj[i].size();j++)
  151.         {
  152.               ie=adj[i][j];
  153.               insert(sg[ie].id,1,nvec,ni,on);
  154.         }
  155.         nf=n;
  156.         for(j=0;j<=(n-1)/bit;j++)
  157.         {
  158.         	if(nvec[j]>0)
  159.         	{
  160. 	        	for(s=0;s<bit;s++)
  161. 	        	{
  162. 	        		if(nvec[j]&(1<<s))
  163. 	        		{
  164. 		        		nf=j*bit+s;
  165. 		        		break;
  166. 		        	}
  167. 	        	}
  168. 	        	break;
  169. 	        }
  170.         }
  171.         mi=find_min(nvec,ni,on);
  172.         if(dp[i+1]<mi)
  173.         {
  174.             dp[i+1]=mi;
  175.             for(j=0;j<=(n-1)/bit;j++)
  176.             {
  177.                vec[i+1][j]=nvec[j];
  178.                ii[i+1][j]=ni[j];
  179.                one[i+1][j]=on[j];
  180. 			}
  181. 		}
  182.         ip=i+1;
  183.         nowt=ls[i];
  184.         id=upper_bound(0,cnt_ls-1,nowt+T);
  185.         if(nowt>mi)
  186.         {
  187.        	   i++;
  188.            continue;
  189.         }
  190.         while(true)
  191.         {
  192.             insert(nf,-1,nvec,ni,on);
  193.             bool hv=false;
  194.             for(j=ip;j<id;j++)
  195.             {
  196.                 for(s=0;s<adj[j].size();s++)
  197.                 {
  198.                     ie=adj[j][s];
  199.                     insert(sg[ie].id,1,nvec,ni,on);
  200.                     if(sg[ie].id<=nf)
  201.                     {
  202.                        nf=sg[ie].id;
  203.                        hv=true;
  204.                     }
  205.                 }
  206.             }
  207.             if(!hv)
  208.             {
  209.             	for(j=nf/bit;j<=(n-1)/bit;j++)
  210.             	{
  211. 	            	if(nvec[j]>0)
  212. 	            	{
  213. 	            		for(s=0;s<bit;s++)
  214. 	            		{
  215. 		            		if(nvec[j]&(1<<s))
  216. 		            		{
  217. 		            			nf=j*bit+s;
  218. 		            			break;
  219. 		            		}
  220. 		            	}
  221. 	            		break;
  222. 	            	}
  223. 	            }
  224. 	            if(j>(n-1)/bit)
  225. 	                nf=n;
  226.             }
  227.             if(id>ip)
  228.             {
  229.             	mi=find_min(nvec,ni,on);
  230.                  if(nowt+T>mi)
  231.                    break;
  232.             }
  233.             nowt+=T;
  234.             ip=upper_bound(0,cnt_ls-1,nowt+T);
  235.             if(id<ip||nf==n)
  236.             {
  237.             	mi=find_min(nvec,ni,on);
  238.                 if(dp[id]<=mi)
  239.                 { 
  240.                    dp[id]=mi;
  241.                    for(j=0;j<=(n-1)/bit;j++)
  242.                    {
  243.                    	   vec[id][j]=nvec[j];
  244.                    	   one[id][j]=on[j];
  245.                    	   ii[id][j]=ni[j];
  246.                    }
  247.                    nxt=id;
  248.                 }
  249.                 else
  250.                    break;
  251.             }
  252.             if(nf==n)
  253.                break;
  254.             swap(id,ip);
  255.         }
  256.         i=max(i+1,nxt-10);
  257.         if(dp[cnt_ls]>-inf)
  258.         {
  259.             for(j=0;j<=(n-1)/bit;j++)
  260.             {
  261.                 if(vec[cnt_ls][j]!=0)
  262.                     break;
  263.             }
  264.             if(j>(n-1)/bit)
  265.             {
  266.                 puts("yes");
  267.                 return 0;
  268.             }
  269.         }
  270.     }
  271.     if(dp[cnt_ls]>-inf)
  272.     {
  273.         for(j=0;j<=(n-1)/bit;j++)
  274.         {
  275.             if(vec[cnt_ls][j]!=0)
  276.                 break;
  277.         }
  278.         if(j>(n-1)/bit)
  279.         {
  280.             puts("yes");
  281.             return 0;
  282.         }
  283.     }
  284.     puts("no");
  285.     return 0;
  286. }
Success #stdin #stdout 0s 53848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
yes
https://ideone.com/g5otEq
language:
C++ (gcc 8.3)
created:
7 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!