제출 #722055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722055		Hyojin	Zoltan (COCI16_zoltan)	C++17	140 / 140	112 ms	7664 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
const int MOD=1e9+7;
const int base=31;
const int N=2e5+5;
const int maxN=2e5;
int mul(int a,int b){return (1ll*a*b)%MOD;}
void add(pii &a,pii b)
{
	if (a.fi<b.fi) a=b;
	else if (a.fi==b.fi) a.se=(a.se+b.se)%MOD;
}
int n,a[N],f[N],cnt,p2[N];
struct fenwickTree
{
	vector<pii>ft;
	fenwickTree(int n)
	{
		ft.resize(n+5);
	}
	pii get(int type,int x)
	{
		pii s={0,1};
		if (type==0) for (;x;x-=x&-x) add(s,ft[x]);
		else for (;x<=n;x+=x&-x) add(s,ft[x]);
		return s;
	}
	void update(int type,int x,pii val)
	{
		if (type==0) for (;x<=n;x+=x&-x) add(ft[x],val);
		else for (;x;x-=x&-x) add(ft[x],val);
	}
};
int main()
{
	#ifdef izumiShiho
    	freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	#endif //izumiShiho
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	fenwickTree fen1(n),fen2(n);
	p2[0]=1;
	for (int i=1;i<=n;i++)
	{
		p2[i]=mul(p2[i-1],2);
		cin>>a[i];
		f[i]=a[i];
	}
	reverse(a+1,a+n+1);
	sort(f+1,f+n+1);
	cnt=unique(f+1,f+n+1)-f-1;
	pii ans={0,1};
	for (int i=1;i<=n;i++)
	{	
		int id=lower_bound(f+1,f+cnt+1,a[i])-f;
		pii x=fen1.get(0,id-1);
		pii y=fen2.get(1,id+1);
		x.fi++;
		y.fi++;
		fen1.update(0,id,x);
		fen2.update(1,id,y);
		pii combine={x.fi+y.fi-1,mul(x.se,y.se)};
		add(ans,combine);
	}
	cout<<ans.fi<<' '<<mul(ans.se,p2[n-ans.fi]);
	return 0;
}

• Subtask 1: 140 / 140