oj.uz

답안 #125777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125777 2019-07-06T11:01:02 Z faustaadp 사다리꼴 (balkan11_trapezoid) C++17
26 / 100
 500 ms 23020 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;
		}
		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;
		}
		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;
		}
		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];
	}
}
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,0);
			}
			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]);
		}
		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:139:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<z.size();i++)
          ~^~~~~~~~~
trapezoid.cpp:182:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~
trapezoid.cpp:170: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 3704 KB Partially correct
8 Partially correct 28 ms 3832 KB Partially correct
9 Partially correct 59 ms 4856 KB Partially correct
10 Partially correct 106 ms 7544 KB Partially correct
11 Partially correct 165 ms 8024 KB Partially correct
12 Partially correct 365 ms 13560 KB Partially correct
13 Partially correct 482 ms 15352 KB Partially correct
14 Execution timed out 581 ms 19696 KB Time limit exceeded
15 Execution timed out 651 ms 18800 KB Time limit exceeded
16 Execution timed out 717 ms 20204 KB Time limit exceeded
17 Execution timed out 761 ms 21640 KB Time limit exceeded
18 Execution timed out 710 ms 20796 KB Time limit exceeded
19 Execution timed out 867 ms 21968 KB Time limit exceeded
20 Execution timed out 950 ms 23020 KB Time limit exceeded