oj.uz

답안 #125821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125821 2019-07-06T12:09:48 Z faustaadp 사다리꼴 (balkan11_trapezoid) C++17
55 / 100
 329 ms 19820 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])
	{
		if(aa<bb)
		{
			LZ[ee*2]=1;
			LZ[ee*2+1]=1;
		}
		LZ[ee]=0;
		ST2[ee]=0;
	}
	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(LZ[ee])
	{
		if(aa<bb)
		{
			LZ[ee*2]=1;
			LZ[ee*2+1]=1;
		}
		LZ[ee]=0;
		ST2[ee]=0;
	}
	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)
{
	if(LZ[ee])
	{
		if(aa<bb)
		{
			LZ[ee*2]=1;
			LZ[ee*2+1]=1;
		}
		LZ[ee]=0;
		ST2[ee]=0;
	}
	if(bb<cc||dd<aa)return ;
	else
	if(cc<=aa&&bb<=dd)
	{
		ST2[ee]=0;
		if(aa<bb)
		{
			LZ[ee*2]=0;
			LZ[ee*2+1]=0;
		}
	}
	else
	{
		ll ce=(aa+bb)/2;
		kos(aa,ce,cc,dd,ee*2);
		kos(ce+1,bb,cc,dd,ee*2+1);
		ST2[ee]=(ST2[ee*2]+ST2[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(n<=40000)
	{
		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;
		for(i=n;i>=1;i--)
		{
			if(que(1,K,me[A[i].se.fi],K,1)<=d[i])
			{
				ll L=1,R=me[A[i].se.fi],C,H=-1;
				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&&d[j]<d[i])
				// 		kos(1,K,me[A[j].se.fi],me[A[j].se.fi],1);
				if(H!=-1)
					kos(1,K,H,me[A[i].se.fi],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
	if(n>5000)
	{
		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;
		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;
			}
		//	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:142:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<z.size();i++)
          ~^~~~~~~~~
trapezoid.cpp:192:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~
trapezoid.cpp:266:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~

Subtask #1
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Partially correct 7 ms 2808 KB Partially correct
4 Correct 10 ms 2936 KB Output is correct
5 Partially correct 19 ms 3064 KB Partially correct
6 Partially correct 29 ms 3320 KB Partially correct
7 Correct 28 ms 3448 KB Output is correct
8 Partially correct 39 ms 3704 KB Partially correct
9 Partially correct 92 ms 4788 KB Partially correct
10 Correct 168 ms 7032 KB Output is correct
11 Partially correct 329 ms 7672 KB Partially correct
12 Partially correct 130 ms 11380 KB Partially correct
13 Partially correct 163 ms 12884 KB Partially correct
14 Partially correct 208 ms 16468 KB Partially correct
15 Partially correct 217 ms 16412 KB Partially correct
16 Partially correct 228 ms 17132 KB Partially correct
17 Partially correct 246 ms 18152 KB Partially correct
18 Partially correct 207 ms 18220 KB Partially correct
19 Partially correct 278 ms 18824 KB Partially correct
20 Partially correct 300 ms 19820 KB Partially correct