Submission #125772

#	Time	Username	Problem	Language	Result	Execution time	Memory
125772		faustaadp	trapezoid (balkan11_trapezoid)	C++17	26 / 100	936 ms	22740 KiB

trapezoid

#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];
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(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(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(bb<cc||dd<aa)return 0;
	else
	if(cc<=aa&&bb<=dd)return ST2[ee];
	else
	{
		ll ce=(aa+bb)/2;
		return ((que(aa,ce,cc,dd,ee*2)+que(ce+1,bb,cc,dd,ee*2+1))%mo);
	}
}
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--)
		{
			if(que(1,K,me[A[i].se.fi],K,1)<=d[i])
			{
				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;
				if(d[now]==1)d2[now]=1;
				else
				{
					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],C,1)+1==d[now])
						{
							H=C;
							L=C+1;
						}
						else
							R=C-1;
					}
					d2[now]=que2(1,K,me[A[now].se.se+1],H,1);
				//	cout<<now<<" "<<d2[now]<<"\n";
				}
			}
			h1=max(h1,d[i]);
		}
		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 (stderr)

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:91:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<z.size();i++)
          ~^~~~~~~~~
trapezoid.cpp:121:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~

• Subtask 1: 26 / 100