oj.uz

답안 #125744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125744 2019-07-06T09:52:29 Z faustaadp 사다리꼴 (balkan11_trapezoid) C++17
40 / 100
 263 ms 17264 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];
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)
{
	if(aa==bb)ST[ee]=dd;
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)
			upd(aa,ce,cc,dd,ee*2);
		else
			upd(ce+1,bb,cc,dd,ee*2+1);
		ST[ee]=max(ST[ee*2],ST[ee*2+1]);
	}
}
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));
	}
}
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--)
		{
			upd(1,K,me[A[i].se.fi],d[i],1);
			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;
			}
			h1=max(h1,d[i]);
		}
	}
	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:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<z.size();i++)
          ~^~~~~~~~~
trapezoid.cpp:101:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<v[i].size();j++)
            ~^~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 5 ms 2680 KB Partially correct
2 Partially correct 5 ms 2812 KB Partially correct
3 Partially correct 5 ms 2808 KB Partially correct
4 Partially correct 5 ms 2808 KB Partially correct
5 Partially correct 7 ms 3064 KB Partially correct
6 Partially correct 9 ms 3192 KB Partially correct
7 Partially correct 10 ms 3320 KB Partially correct
8 Partially correct 12 ms 3448 KB Partially correct
9 Partially correct 22 ms 4216 KB Partially correct
10 Partially correct 41 ms 5880 KB Partially correct
11 Partially correct 53 ms 6520 KB Partially correct
12 Partially correct 124 ms 10072 KB Partially correct
13 Partially correct 149 ms 11636 KB Partially correct
14 Partially correct 181 ms 14192 KB Partially correct
15 Partially correct 201 ms 14024 KB Partially correct
16 Partially correct 224 ms 14928 KB Partially correct
17 Partially correct 233 ms 15724 KB Partially correct
18 Partially correct 189 ms 15856 KB Partially correct
19 Partially correct 231 ms 16620 KB Partially correct
20 Partially correct 263 ms 17264 KB Partially correct