Submission #125980

# Submission time Handle Problem Language Result Execution time Memory
125980 2019-07-06T15:50:16 Z faustaadp trapezoid (balkan11_trapezoid) C++17
45 / 100
500 ms 19312 KB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n,i,ta,tb,tc,td,j,h1,h2,d[101010],d2[101010],mo=30013,K,ST[808080],ST2[808080],D[101010],LZ[808080];
vector<int> v[101010],z;
pair<pair<int,int>,pair<int,int> > A[101010];
map<int,int> me;
int depe(int aa)
{
	if(d[aa]==-1)
	{
		d[aa]=0;
		int ii;
		for(ii=0;ii<v[aa].size();ii++)
			d[aa]=max(d[aa],depe(v[aa][ii]));
		d[aa]++;
	}
	return d[aa];
}
int depe2(int aa)
{
	if(depe(aa)==1)return 1;
	if(d2[aa]==-1)
	{
		d2[aa]=0;
		int ii;
		for(ii=0;ii<v[aa].size();ii++)
			if(depe(aa)==depe(v[aa][ii])+1)
				d2[aa]=(d2[aa]+depe2(v[aa][ii]))%mo;
	}
	return d2[aa];
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
	if(LZ[ee]!=-1)
	{
		if(aa<bb)
		{
			LZ[ee*2]=LZ[ee];
			LZ[ee*2+1]=LZ[ee];
		}
		ST2[ee]=0;
		ST[ee]=LZ[ee];
		LZ[ee]=-1;
	}
	if(aa==bb)
	{
		ST[ee]=dd;
		ST2[ee]+=ff;
		ST2[ee]%=mo;
	}
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,dd,ee*2,ff);
		else
			upd(ce+1,bb,cc,dd,ee*2+1,ff);
		ST[ee]=max(ST[ee*2],ST[ee*2+1]);
		ST2[ee]=(ST2[ee*2]+ST2[ee*2+1])%mo;
	}
}
ll que(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(LZ[ee]!=-1)
	{
		if(aa<bb)
		{
			LZ[ee*2]=LZ[ee];
			LZ[ee*2+1]=LZ[ee];
		}
		ST2[ee]=0;
		ST[ee]=LZ[ee];
		LZ[ee]=-1;
	}
	if(bb<cc||dd<aa)return 0;
	else
	if(cc<=aa&&bb<=dd)return ST[ee];
	else
	{
		ll ce=(aa+bb)/2;
		return max(que(aa,ce,cc,dd,ee*2),que(ce+1,bb,cc,dd,ee*2+1));
	}
}
ll que2(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	if(LZ[ee]!=-1)
	{
		if(aa<bb)
		{
			LZ[ee*2]=LZ[ee];
			LZ[ee*2+1]=LZ[ee];
		}
		ST2[ee]=0;
		ST[ee]=LZ[ee];
		LZ[ee]=-1;
	}
	if(bb<cc||dd<aa)return 0;
	else
	if(cc<=aa&&bb<=dd)return ST2[ee];
	else
	{
		ll ce=(aa+bb)/2;
		return ((que2(aa,ce,cc,dd,ee*2)+que2(ce+1,bb,cc,dd,ee*2+1))%mo);
	}
}
void kos(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
	if(LZ[ee]!=-1)
	{
		//while(1);
		if(aa<bb)
		{
			LZ[ee*2]=LZ[ee];
			LZ[ee*2+1]=LZ[ee];
		}
		ST2[ee]=0;
		ST[ee]=LZ[ee];
		LZ[ee]=-1;
	}
	if(bb<cc||dd<aa)return ;
	else
	//if(cc<=aa&&bb<=dd)
	if(aa==bb)
	{
		ST2[ee]=0;
		ST[ee]=ff;
		if(aa<bb)
		{
			LZ[ee*2]=ff;
			LZ[ee*2+1]=ff;
		}
	}
	else
	{
		ll ce=(aa+bb)/2;
		kos(aa,ce,cc,dd,ee*2,ff);
		kos(ce+1,bb,cc,dd,ee*2+1,ff);
		ST2[ee]=(ST2[ee*2]+ST2[ee*2+1])%mo;
		ST[ee]=max(ST[ee*2],ST[ee*2+1]);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	K=n*2;
	for(i=1;i<=n;i++)
	{
		cin>>ta>>tb>>tc>>td;
		A[i]=mp(mp(ta,tb),mp(tc,td));
		z.pb(tc);
		z.pb(td+1);
	}
	sort(z.begin(),z.end());
	for(i=0;i<z.size();i++)
		me[z[i]]=i+1;
	if(1)
	{
		sort(A+1,A+1+n);
		for(i=1;i<=n;i++)
		{
			int L=i+1,R=n,C,H=0;
			while(L<=R)
			{
				C=(L+R)/2;
				if(A[i].fi.se<A[C].fi.fi)
				{
					H=C;
					R=C-1;
				}
				else
					L=C+1;
			}
			if(H)
				v[H].pb(i);
		}
		//return 0;
		for(i=n;i>=1;i--)d[i]=1;
		for(i=n;i>=1;i--)d2[i]=1;
		memset(LZ,-1,sizeof(LZ));
		for(i=n;i>=1;i--)
		{
			if(que(1,K,me[A[i].se.fi],K,1)<=d[i])
			{
				ll L=K+1,R=me[A[i].se.fi],C,H=-1;
				R=0;
				// L=1e18;
				// R=-1e18;
				// while(L<=R)
				// {
				// 	C=(L+R)/2;
				// 	if(que(1,K,C,me[A[i].se.fi],1)<d[i])
				// 	{
				// 		H=C;
				// 		R=C-1;
				// 	}
				// 	else
				// 		L=C+1;
				// } 
				for(j=i;j<=n;j++)
					if(A[j].se.fi<A[i].se.fi&&que(1,K,me[A[j].se.fi],me[A[j].se.fi],1)<d[i]&&(que2(1,K,me[A[j].se.fi],me[A[j].se.fi],1)>0))
					{
						L=min(L,(ll)me[A[j].se.fi]);
						//R=max(R,(ll)me[A[j].se.fi]);
				//		kos(1,K,me[A[j].se.fi],me[A[j].se.fi],1,d[i]);
					}
			//	cout<<L<<" "<<me[A[i].se.fi]<<"\n";
			//	return 0;
				if(L<=me[A[i].se.fi])
				kos(1,K,L,me[A[i].se.fi],1,d[i]);
				//if(H!=-1)
				//cout<<i<<" "<<me[A[i].se.fi]<<" "<<H<<"_\n";
				//cout<<"upd "<<i<<" "<<me[A[i].se.fi]<<" "<<d[i]<<"___\n";
				upd(1,K,me[A[i].se.fi],d[i],1,d2[i]);
			}
			for(j=0;j<v[i].size();j++)
			{
				int now=v[i][j];
				d[now]=que(1,K,me[A[now].se.se+1],K,1)+1;
				ll L=me[A[now].se.se+1],R=K,C,H=0;
				while(L<=R)
				{
					C=(L+R)/2;
					if(que(1,K,me[A[now].se.se+1],C,1)+1==d[now])
					{
						H=C;
						R=C-1;
					}
					else
						L=C+1;
				}
				L=H,R=K;
				ll H2=K;
				while(L<=R)
				{
					C=(L+R)/2;
					if((que(1,K,C,K,1)+1)!=d[now])
					{
						H2=C-1;
						R=C-1;
					}
					else
						L=C+1;
				}
				if(d[now]==1)d2[now]=1;
				else
				{
			//		cout<<now<<"___ "<<H<<" "<<H2<<"@\n";
					d2[now]=que2(1,K,H,H2,1);
				}
			}
		//	cout<<i<<" "<<d[i]<<" "<<d2[i]<<"\n";
			h1=max(h1,d[i]);
		}
	//	cout<<"A";
		for(i=1;i<=n;i++)
			if(h1==d[i])
				h2=(h2+d2[i])%mo;
	}
	else
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(A[i].fi.se<A[j].fi.fi&&A[i].se.se<A[j].se.fi)
					v[i].pb(j);
		memset(d,-1,sizeof(d));
		memset(d2,-1,sizeof(d2));
		for(i=1;i<=n;i++)
			h1=max(h1,depe(i));
		for(i=1;i<=n;i++)
			if(depe(i)==h1)
				h2=(h2+depe2(i))%mo;
	}
	cout<<h1<<" "<<h2<<"\n";	
}	

Compilation message

trapezoid.cpp: In function 'int depe(int)':
trapezoid.cpp:18:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[aa].size();ii++)
            ~~^~~~~~~~~~~~~
trapezoid.cpp: In function 'int depe2(int)':
trapezoid.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ii=0;ii<v[aa].size();ii++)
            ~~^~~~~~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:160:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<z.size();i++)
          ~^~~~~~~~~
trapezoid.cpp:190:14: warning: variable 'R' set but not used [-Wunused-but-set-variable]
     ll L=K+1,R=me[A[i].se.fi],C,H=-1;
              ^
trapezoid.cpp:190:31: warning: unused variable 'C' [-Wunused-variable]
     ll L=K+1,R=me[A[i].se.fi],C,H=-1;
                               ^
trapezoid.cpp:190:33: warning: unused variable 'H' [-Wunused-variable]
     ll L=K+1,R=me[A[i].se.fi],C,H=-1;
                                 ^
trapezoid.cpp:221:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 7 ms 5880 KB Output is correct
2 Correct 7 ms 5880 KB Output is correct
3 Correct 11 ms 6008 KB Output is correct
4 Correct 12 ms 6008 KB Output is correct
5 Correct 125 ms 6264 KB Output is correct
6 Correct 229 ms 6392 KB Output is correct
7 Correct 34 ms 6520 KB Output is correct
8 Correct 476 ms 6776 KB Output is correct
9 Execution timed out 1074 ms 7720 KB Time limit exceeded
10 Correct 254 ms 9712 KB Output is correct
11 Execution timed out 1085 ms 9976 KB Time limit exceeded
12 Execution timed out 1091 ms 12912 KB Time limit exceeded
13 Execution timed out 1082 ms 14836 KB Time limit exceeded
14 Execution timed out 1080 ms 16236 KB Time limit exceeded
15 Execution timed out 1075 ms 17516 KB Time limit exceeded
16 Execution timed out 1076 ms 17268 KB Time limit exceeded
17 Execution timed out 1076 ms 18412 KB Time limit exceeded
18 Execution timed out 1069 ms 19312 KB Time limit exceeded
19 Execution timed out 1089 ms 18540 KB Time limit exceeded
20 Execution timed out 1066 ms 19296 KB Time limit exceeded