oj.uz

답안 #445509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445509 2021-07-18T11:58:46 Z keta_tsimakuridze Zoltan (COCI16_zoltan) C++14
140 / 140
 605 ms 23368 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,a[N],b[N],n,pwr[N];
pair<int,int> tree[4*N][2],l[N][2];
map<int,int> ind;
void upd(pii &a,pii b){
	if(a.f == b.f) {
		a.s = (a.s + b.s)%mod;
	}
	else if(a.f < b.f) {
		a.s = b.s;
		a.f = b.f;
	}
}
void update(int u,int ind,int l,int r,int val1,int val2,int t) {
	if(l>ind || r<ind) return;
	if(l==r) {
		upd(tree[u][t],{val1,val2});
		return;
	}
	int mid = (l+r)/2;
	update(2*u,ind,l,mid,val1,val2,t);
	update(2*u+1,ind,mid+1,r,val1,val2,t);
	tree[u][t] = {0,0};
	upd(tree[u][t],tree[2*u][t]);
	upd(tree[u][t],tree[2*u+1][t]);
}
pii getans(int u,int start,int end,int l,int r,int t) {
	if(l > end || r<start) return {0,0};
	if(start<=l && r<=end) return tree[u][t];
	int mid = (l+r)/2;
	pii g1 = getans(2*u,start,end,l,mid,t);
	pii g2 = getans(2*u+1,start,end,mid+1,r,t);
	upd(g1,g2);
	return g1;
}
 main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i] = a[i];
	}
	sort(b+1,b+n+1);
	int idx = 0;
	b[0] = -1;
	pwr[0] = 1;
	for(int i=1;i<=n;i++){
		pwr[i] = pwr[i-1] * 2 % mod;
		if(b[i]!=b[i-1]) idx++;
		ind[b[i]] = idx;
	}
	for(int i=n;i>=2;i--){
		a[i] = ind[a[i]];
		pii p = getans(1,1,a[i]-1,1,n,1);
		p.f++;
		if(p.f == 1) p.s = 1;
		upd(l[a[i]][1],p);
		update(1,a[i],1,n,p.f,p.s,1);
		
			 p = getans(1,a[i]+1,n,1,n,0);
			p.f++;
			if(p.f == 1) p.s = 1;
			update(1,a[i],1,n,p.f,p.s,0);
			upd(l[a[i]][0],p);
		
	}
	l[0][1] = {0,1};
	l[idx+1][0] = {0,1}; 
	pii ans;
	ans = {0,0};
	for(int i=idx;i>=0;i--){
		upd(l[i][0],l[i+1][0]);
	}
	for(int i=0;i<=idx;i++) {
		upd(ans,{l[i][1].f + l[i+1][0].f,(long long) l[i][1].s * l[i+1][0].s %mod* pwr[n -l[i][1].f - l[i+1][0].f - 1]%mod});
	}
	// 
	a[1] = ind[a[1]];
	pii p = getans(1,a[1]+1,n,1,n,0);
	p.f++;
	if(p.f==1) p.s = 1;
	for(int i=0; i<a[1]; i++) {
		upd(ans,{l[i][1].f + p.f,(long long) l[i][1].s * p.s %mod* pwr[n -l[i][1].f - p.f]%mod});
		
	}
 
	cout<<ans.f<<" "<<ans.s;
	
}

Compilation message

zoltan.cpp:41:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 |  main(){
      |  ^~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 344 ms 20284 KB Output is correct
12 Correct 311 ms 18808 KB Output is correct
13 Correct 273 ms 14256 KB Output is correct
14 Correct 384 ms 18912 KB Output is correct
15 Correct 487 ms 21368 KB Output is correct
16 Correct 605 ms 23368 KB Output is correct
17 Correct 441 ms 20144 KB Output is correct
18 Correct 471 ms 20036 KB Output is correct
19 Correct 422 ms 20196 KB Output is correct
20 Correct 434 ms 20124 KB Output is correct