Submission #532932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
532932	2022-03-04T08:51:23 Z	colazcy	Zoltan (COCI16_zoltan)	C++17	140 / 140	119 ms	16736 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5084 KB	Output is correct
2	Correct	3 ms	4956 KB	Output is correct
3	Correct	2 ms	4944 KB	Output is correct
4	Correct	4 ms	5028 KB	Output is correct
5	Correct	3 ms	4944 KB	Output is correct
6	Correct	3 ms	4944 KB	Output is correct
7	Correct	3 ms	5072 KB	Output is correct
8	Correct	4 ms	5072 KB	Output is correct
9	Correct	5 ms	5032 KB	Output is correct
10	Correct	4 ms	5072 KB	Output is correct
11	Correct	75 ms	14800 KB	Output is correct
12	Correct	63 ms	13556 KB	Output is correct
13	Correct	62 ms	13120 KB	Output is correct
14	Correct	71 ms	11968 KB	Output is correct
15	Correct	101 ms	13724 KB	Output is correct
16	Correct	97 ms	15192 KB	Output is correct
17	Correct	103 ms	16644 KB	Output is correct
18	Correct	114 ms	16736 KB	Output is correct
19	Correct	101 ms	16552 KB	Output is correct
20	Correct	119 ms	16644 KB	Output is correct