Submission #200226

#	Time	Username	Problem	Language	Result	Execution time	Memory
200226		hamzqq9	Zoltan (COCI16_zoltan)	C++14	140 / 140	478 ms	23648 KiB

zoltan

#include<bits/stdc++.h>
#define st first
#define nd second
#define orta ((bas+son)>>1)
#define ll long long
#define ii pair<int,int>
#define N 200005
#define MOD 1000000007
#define inf 1000000001
using namespace std;

int n,cnt;
int a[N];
ii lids[2][N<<2]; // 0 lis 1 lds
ii c[2][N];

int mul(int x,int y) {
	
	return (ll)x*y%MOD;

}

int add(int x,int y) {

	x+=y;
	if(x>=MOD) x-=MOD;
	if(x<0) x+=MOD;
	return x;

}

ii merge(ii a,ii b) {

	if(a.st>b.st) return a;
	if(b.st>a.st) return b;
	return {a.st,add(a.nd,b.nd)};

}

ii get(int node,int bas,int son,int l,int r,int w) {

	if(bas>=l && son<=r) return lids[w][node];
	if(orta>=l && orta+1<=r) 
		return merge(get(node<<1,bas,orta,l,r,w),get(node<<1|1,orta+1,son,l,r,w));
	if(orta>=l) return get(node<<1,bas,orta,l,r,w);
	return get(node<<1|1,orta+1,son,l,r,w); 

}

void up(int node,int bas,int son,int x,ii val,int w) {

	if(bas>x || son<x) return ;
	if(bas==x && son==x) {
		lids[w][node]=merge(lids[w][node],val);
		return ;
	}
	up(node<<1,bas,orta,x,val,w);
	up(node<<1|1,orta+1,son,x,val,w);
	lids[w][node]=merge(lids[w][node<<1],lids[w][node<<1|1]);

}

void compress() {

	vector<int> v(a+1,a+1+n);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	map<int,int> mp;
	for(int i:v) mp[i]=++cnt;
	for(int i=1;i<=n;i++) a[i]=mp[a[i]];

}

int main() {

	scanf("%d",&n);
	n+=2;
	for(int i=2;i<=n-1;i++) scanf("%d",a+i);
	a[n]=inf;
	compress();
	reverse(a+1,a+1+n);
	up(1,1,cnt,1,{0,1},0);
	up(1,1,cnt,cnt,{0,1},1);
	for(int i=2;i<=n-1;i++) {
		ii res0=get(1,1,cnt,1,a[i]-1,0);
		res0.st++;
		up(1,1,cnt,a[i],res0,0);
		ii res1=get(1,1,cnt,a[i]+1,cnt,1);
		res1.st++;
		up(1,1,cnt,a[i],res1,1);
		c[0][i]=res0;
		c[1][i]=res1;
	}
	ii ans={0,0};
	for(int i=2;i<=n-1;i++) {
		ii mrg={c[0][i].st+c[1][i].st-1,mul(c[0][i].nd,c[1][i].nd)};
		if(mrg.st>ans.st) {
			ans.st=mrg.st;
			ans.nd=0;
		}
		if(mrg.st==ans.st) {
			ans.nd=add(ans.nd,mrg.nd);
		}
	}
	for(int i=1;i<=n-ans.st-2;i++) ans.nd=mul(ans.nd,2);
	printf("%d %d",ans.st,ans.nd);
 	
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
zoltan.cpp:78:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=2;i<=n-1;i++) scanf("%d",a+i);
                          ~~~~~^~~~~~~~~~

• Subtask 1: 140 / 140