Submission #535818

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535818	2022-03-11T11:04:39 Z	new_acc	Zoltan (COCI16_zoltan)	C++14	119 / 140	236 ms	14624 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

119.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 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	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	134 ms	11436 KB	Output is correct
12	Correct	127 ms	10008 KB	Output is correct
13	Correct	114 ms	9484 KB	Output is correct
14	Incorrect	139 ms	10268 KB	Output isn't correct
15	Incorrect	202 ms	12752 KB	Output isn't correct
16	Incorrect	236 ms	14624 KB	Output isn't correct
17	Correct	155 ms	13176 KB	Output is correct
18	Correct	177 ms	13152 KB	Output is correct
19	Correct	167 ms	13208 KB	Output is correct
20	Correct	159 ms	13056 KB	Output is correct