Submission #535820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535820	2022-03-11T11:10:14 Z	new_acc	Zoltan (COCI16_zoltan)	C++14	140 / 140	207 ms	12760 KB

zoltan

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const ll INF=1e18;
const ll mod=1e9+7;
const int SS=1<<18;
pair<int,int> dp1[N],dp2[N];
struct tr{
	pair<int,int> seg[(SS<<1)+10];
	pair<int,int> comb(pair<int,int> a,pair<int,int> b){
		if(a.fi>b.fi) return a;
		if(b.fi>a.fi) return b;
		return {a.fi,(a.se+b.se)%mod};
	}
	void upd(int ind,pair<int,int> val){
		ind+=SS;
		seg[ind]=comb(seg[ind],val);
		for(ind>>=1;ind>0;ind>>=1) seg[ind]=comb(seg[ind<<1],seg[(ind<<1)+1]);
	}
	pair<int,int> Query(int a,int b){
		pair<int,int> res={0,0};
		for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
			if(!(a&1)) res=comb(res,seg[a+1]);
			if(b&1) res=comb(res,seg[b-1]);
		}
		return res;
	}
}ros,mal;
int t[N];
pair<int,int> skal[N];
int pot[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		skal[i]={t[i],i};
	}
	sort(skal+1,skal+1+n);
	int curr=0;
	for(int i=1;i<=n;i++){
		if(i==1 or skal[i].fi!=skal[i-1].fi) curr++;
		t[skal[i].se]=curr;
	}
	ros.upd(0,{0,1}),mal.upd(n+1,{0,1});
	pot[0]=1;
	for(int i=1;i<=n;i++) pot[i]=(pot[i-1]*2LL)%mod;
	int maxi=0;
	for(int i=n;i>=1;i--){
		dp1[i]=mal.Query(t[i]+1,n+1);
		dp2[i]=ros.Query(0,t[i]-1);
		dp1[i].fi++,dp2[i].fi++;
		ros.upd(t[i],dp2[i]),mal.upd(t[i],dp1[i]);
		maxi=max(maxi,dp1[i].fi+dp2[i].fi-1);
	}
	ll res=0;
	for(int i=1;i<=n;i++)
		if(dp1[i].fi+dp2[i].fi-1==maxi) (res+=((ll)pot[n-maxi]*(((ll)dp1[i].se*(ll)dp2[i].se)%mod))%mod)%=mod;
	cout<<maxi<<" "<<res<<"\n";
}
int main(){
	solve();
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	380 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	122 ms	10196 KB	Output is correct
12	Correct	105 ms	8904 KB	Output is correct
13	Correct	99 ms	8484 KB	Output is correct
14	Correct	133 ms	9012 KB	Output is correct
15	Correct	173 ms	11088 KB	Output is correct
16	Correct	207 ms	12760 KB	Output is correct
17	Correct	158 ms	11852 KB	Output is correct
18	Correct	149 ms	11816 KB	Output is correct
19	Correct	146 ms	11860 KB	Output is correct
20	Correct	153 ms	11824 KB	Output is correct