Submission #361427

#	Time	Username	Problem	Language	Result	Execution time	Memory
361427		pure_mem	Zoltan (COCI16_zoltan)	C++14	140 / 140	121 ms	12620 KiB

zoltan

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 2e5 + 3, mod = 1e9 + 7;

int n, a[N], all;
pair<int, ll> fw[N], dp1[N], dp2[N];

inline void upd(int v, pair<int, ll> val){
	for(;v <= all;v |= v + 1){
		if(fw[v].X < val.X)
			fw[v] = val;
		else if(fw[v].X == val.X)
			fw[v].Y = (fw[v].Y + val.Y) % mod;
	}
}

inline pair<int, ll> get(int v){
	pair<int, ll> val = MP(0, 1);
	for(;v >= 0;v = (v & (v + 1)) - 1){
		if(fw[v].X > val.X)
			val = fw[v];
		else if(fw[v].X == val.X)
			val.Y = (fw[v].Y + val.Y) % mod;
	}
	return val;
}

inline void squiz(){
	vector< pair<int, int> > tmp;
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		scanf("%d", a + i), tmp.push_back(MP(a[i], i));
	sort(tmp.begin(), tmp.end());
	for(int i = 0;i < (int)tmp.size();i++){
		if(i == 0 || tmp[i].X != tmp[i - 1].X)
			all++;
		a[tmp[i].Y] = all;
	}
}

int main () {
	squiz();
	for(int i = n;i >= 1;i--){
		dp1[i] = get(a[i] - 1), dp1[i].X += 1;
		if(dp1[i].X == 1)
			dp1[i].Y = 1;
		upd(a[i], dp1[i]);
	}
	memset(fw, 0, sizeof(fw));
	ll ans = 1;
	int mx = 0;
	for(int i = n;i >= 1;i--){
		dp2[i] = get(all - a[i]), dp2[i].X += 1;
		if(dp2[i].X == 1)
			dp2[i].Y = 1;
		upd(all - a[i] + 1, dp2[i]);
	}	
	for(int i = n;i >= 1;i--){
		if(dp1[i].X + dp2[i].X - 1 > mx){
			mx = dp1[i].X + dp2[i].X - 1, ans = dp1[i].Y * dp2[i].Y % mod;
		}
		else if(dp1[i].X + dp2[i].X - 1 == mx){
			ans = (ans + (dp1[i].Y * dp2[i].Y % mod)) % mod;
		}
	}
	for(int i = 1;i <= n - mx;i++)
		ans = ans * 2 % mod;
	printf("%d %lld", mx, ans);
}

Compilation message (stderr)

zoltan.cpp: In function 'void squiz()':
zoltan.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
zoltan.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d", a + i), tmp.push_back(MP(a[i], i));
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 140 / 140