Submission #722055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
722055	2023-04-11T11:21:16 Z	Hyojin	Zoltan (COCI16_zoltan)	C++17	140 / 140	112 ms	7664 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	69 ms	5760 KB	Output is correct
12	Correct	54 ms	5076 KB	Output is correct
13	Correct	48 ms	4772 KB	Output is correct
14	Correct	78 ms	5332 KB	Output is correct
15	Correct	94 ms	6676 KB	Output is correct
16	Correct	112 ms	7664 KB	Output is correct
17	Correct	72 ms	7052 KB	Output is correct
18	Correct	71 ms	7072 KB	Output is correct
19	Correct	71 ms	6996 KB	Output is correct
20	Correct	85 ms	7064 KB	Output is correct