oj.uz

답안 #125779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125779 2019-07-06T11:04:34 Z faustaadp 사다리꼴 (balkan11_trapezoid) C++17
26 / 100
 500 ms 22896 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 ((que(aa,ce,cc,dd,ee*2)+que(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(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])
			{
				ll L=me[A[i].se.fi],R,C,H=0;
				while(L<=R)
				{
					C=(L+R)/2;
					if(que(1,K,me[A[i].se.fi],C,1)<d[i])
					{
						H=C;
						R=C-1;
					}
					else
						L=C+1;
				}
				kos(1,K,me[A[i].se.fi],H,1);
				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],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);
			}
			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:185:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~
trapezoid.cpp:173:10: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
      C=(L+R)/2;
        ~~^~~

Subtask #1
26.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 6 ms 2808 KB Partially correct
4 Partially correct 7 ms 2936 KB Partially correct
5 Partially correct 12 ms 3192 KB Partially correct
6 Partially correct 16 ms 3448 KB Partially correct
7 Partially correct 18 ms 3576 KB Partially correct
8 Partially correct 28 ms 3832 KB Partially correct
9 Partially correct 58 ms 4732 KB Partially correct
10 Partially correct 103 ms 7336 KB Partially correct
11 Partially correct 161 ms 7800 KB Partially correct
12 Partially correct 373 ms 13428 KB Partially correct
13 Partially correct 472 ms 15092 KB Partially correct
14 Execution timed out 581 ms 19568 KB Time limit exceeded
15 Execution timed out 644 ms 18856 KB Time limit exceeded
16 Execution timed out 686 ms 19920 KB Time limit exceeded
17 Execution timed out 736 ms 21504 KB Time limit exceeded
18 Execution timed out 705 ms 20712 KB Time limit exceeded
19 Execution timed out 892 ms 21628 KB Time limit exceeded
20 Execution timed out 945 ms 22896 KB Time limit exceeded