Submission #200226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200226	2020-02-05T17:26:47 Z	hamzqq9	Zoltan (COCI16_zoltan)	C++14	140 / 140	478 ms	23648 KB

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

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	6 ms	504 KB	Output is correct
8	Correct	6 ms	504 KB	Output is correct
9	Correct	6 ms	504 KB	Output is correct
10	Correct	6 ms	504 KB	Output is correct
11	Correct	252 ms	20220 KB	Output is correct
12	Correct	212 ms	18768 KB	Output is correct
13	Correct	195 ms	14064 KB	Output is correct
14	Correct	301 ms	19152 KB	Output is correct
15	Correct	401 ms	21708 KB	Output is correct
16	Correct	478 ms	23648 KB	Output is correct
17	Correct	315 ms	21620 KB	Output is correct
18	Correct	300 ms	21596 KB	Output is correct
19	Correct	322 ms	21596 KB	Output is correct
20	Correct	313 ms	21592 KB	Output is correct