oj.uz

답안 #535818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535818 2022-03-11T11:04:39 Z new_acc Zoltan (COCI16_zoltan) C++14
119 / 140
 236 ms 14624 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
119.0 / 140.0

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