Submission #532932

#	Time	Username	Problem	Language	Result	Execution time	Memory
532932		colazcy	Zoltan (COCI16_zoltan)	C++17	140 / 140	119 ms	16736 KiB

zoltan

#include <iostream>
#include <algorithm>
#include <cassert>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 2e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
constexpr int add(const int a,const int b){return a + b >= mod ? a + b - mod : a + b;}
constexpr int sub(const int a,const int b){return a >= b ? a - b : a - b + mod;}
constexpr int mul(const int a,const int b){return 1ll * a * b % mod;}

int n,val[maxn],lis_len[maxn],lis_count[maxn],lds_len[maxn],lds_count[maxn],t[maxn];
namespace fenwick{
	constexpr int lowbit(const int x){return x & (-x);}
	int f[maxn];
	void modify(int pos,const int v){
		for(;pos <= n + 1;pos += lowbit(pos))f[pos] = add(f[pos],v);
	}
	int query(int pos){
		int res = 0;
		for(;pos;pos -= lowbit(pos))res = add(res,f[pos]);
		return res;
	}
	int query(const int l,const int r){return sub(query(r),query(l - 1));}
}
using pir = std::pair<int,int>;
std::vector<pir> vec[maxn];
void solve_lis(){
	std::fill_n(t + 1,n,-inf);
	lis_count[n + 1] = 1;
	per(i,n,1){
		let p = std::lower_bound(t + 1,t + n + 1,val[i],std::greater<int>()) - t;
		lis_len[i] = p;
		t[p] = val[i];
	}
	rep(i,1,n)vec[lis_len[i]].emplace_back(val[i],i);
	vec[0].emplace_back(inf,n + 1);
	rep(i,1,n)std::sort(vec[i].begin(),vec[i].end(),std::greater<pir>());
	rep(i,1,n){
		auto it = vec[i - 1].begin();
		for(let &pir : vec[i]){
			while(it != vec[i - 1].end() && it->first > pir.first){
				fenwick::modify(it->second,lis_count[it->second]);
				// debug("ins : %d\n",it->second);
				it++;
			}
			// debug("ques : %d\n",pir.second);
			lis_count[pir.second] = fenwick::query(pir.second + 1,n + 1);
		}
		for(auto p = vec[i - 1].begin();p != it;p++)fenwick::modify(p->second,sub(0,lis_count[p->second]));
	}
	// rep(i,1,n)debug("%d ",lis_len[i]);
	// debug("\n");
	// rep(i,1,n)debug("%d ",lis_count[i]);
	// debug("\n");
}

void solve_lds(){
	std::fill_n(t + 1,n,inf);
	lds_count[n + 1] = 1;
	per(i,n,1){
		let p = std::lower_bound(t + 1,t + n + 1,val[i]) - t;
		lds_len[i] = p;
		t[p] = val[i];
	}
	rep(i,0,n)vec[i].clear();
	rep(i,1,n)vec[lds_len[i]].emplace_back(val[i],i);
	vec[0].emplace_back(-inf,n + 1);
	rep(i,1,n)std::sort(vec[i].begin(),vec[i].end());
	rep(i,1,n){
		auto it = vec[i - 1].begin();
		for(let &pir : vec[i]){
			while(it != vec[i - 1].end() && it->first < pir.first){
				fenwick::modify(it->second,lds_count[it->second]);
				// debug("ins : %d\n",it->second);
				it++;
			}
			// debug("ques : %d\n",pir.second);
			lds_count[pir.second] = fenwick::query(pir.second + 1,n + 1);
		}
		for(auto p = vec[i - 1].begin();p != it;p++)fenwick::modify(p->second,sub(0,lds_count[p->second]));
	}
	// rep(i,1,n)debug("%d ",lds_len[i]);
	// debug("\n");
	// rep(i,1,n)debug("%d ",lds_count[i]);
	// debug("\n");
}
int main(){
// #ifndef ONLINE_JUDGE
// 	std::freopen("fufu.in","r",stdin);
// #endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n;
	rep(i,1,n)std::cin >> val[i];
	solve_lis();
	solve_lds();

	int ans_len = 0,ans_count = 0;
	
	rep(i,1,n)ans_len = std::max(ans_len,lis_len[i] + lds_len[i] - 1);
	int pw = 1;
	repn(n - ans_len)pw = add(pw,pw);
	rep(i,1,n)
		if(lis_len[i] + lds_len[i] - 1 == ans_len)
			ans_count = add(ans_count,mul(pw,mul(lds_count[i],lis_count[i])));
	std::cout << ans_len << " " << ans_count << "\n";
	// rep(i,1,n)debug("%d ",lis_len[i]);
	// debug("\n");
	// rep(i,1,n)debug("%d ",lds_len[i]);
	// debug("\n");
	
	return 0;
}

• Subtask 1: 140 / 140