oj.uz

답안 #125768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125768 2019-07-06T10:30:46 Z faustaadp 사다리꼴 (balkan11_trapezoid) C++17
34 / 100
 500 ms 21876 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];
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;
	}
	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,C,K,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

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

Subtask #1
34.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 4 ms 2808 KB Partially correct
2 Partially correct 4 ms 2808 KB Partially correct
3 Partially correct 5 ms 2808 KB Partially correct
4 Partially correct 7 ms 2936 KB Partially correct
5 Partially correct 10 ms 3112 KB Partially correct
6 Partially correct 14 ms 3448 KB Partially correct
7 Partially correct 16 ms 3576 KB Partially correct
8 Partially correct 22 ms 3704 KB Partially correct
9 Partially correct 44 ms 4700 KB Partially correct
10 Partially correct 84 ms 7008 KB Partially correct
11 Partially correct 121 ms 7804 KB Partially correct
12 Partially correct 272 ms 12660 KB Partially correct
13 Partially correct 344 ms 14708 KB Partially correct
14 Partially correct 421 ms 18396 KB Partially correct
15 Partially correct 449 ms 18516 KB Partially correct
16 Partially correct 483 ms 19436 KB Partially correct
17 Execution timed out 519 ms 20464 KB Time limit exceeded
18 Partially correct 474 ms 20432 KB Partially correct
19 Execution timed out 573 ms 21100 KB Time limit exceeded
20 Execution timed out 644 ms 21876 KB Time limit exceeded