oj.uz

답안 #535820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535820 2022-03-11T11:10:14 Z new_acc Zoltan (COCI16_zoltan) C++14
140 / 140
 207 ms 12760 KB 
#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

# 결과 실행 시간 메모리 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