Submission #535818

#	Time	Username	Problem	Language	Result	Execution time	Memory
535818		new_acc	Zoltan (COCI16_zoltan)	C++14	119 / 140	236 ms	14624 KiB

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: 119 / 140