Submission #52040

#	Time	Username	Problem	Language	Result	Execution time	Memory
52040		Adhyyan1252	Zoltan (COCI16_zoltan)	C++11	133 / 140	990 ms	25504 KiB

zoltan

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, ll> ii;
#define LMAX 200005
const ll mod = 1000000007;
int n; 
vector<ll> a;
int unum = 1;
void compress(){
	map<int, int> comp;
	for(int i = 0; i < a.size(); i++){
		comp.insert({a[i], -1});
	}
	for(auto it = comp.begin(); it != comp.end(); it++){
		it->second = unum++;
	}
	for(int i = 0; i < a.size(); i++){
		a[i] = comp[a[i]];
	}
}

ii merge(ii a, ii b){
	if(a.first > b.first){
		return a;
	}else if(b.first > a.first){
		return b;
	}else{
		a.second = (a.second + b.second)%mod;
		return a;
	}
}
ii t[4*LMAX];
void upd(int i, int s, int e, int indx, ii val){
	if(s == e){
		t[i] = merge(t[i], val);
		return;
	}
	int m = (s + e)>>1;
	if(indx <= m){
		upd(i*2, s, m, indx, val);
	}else{
		upd(i*2+1, m+1, e, indx, val);
	}
	t[i] = merge(t[i*2], t[i*2+1]);
}

ll POW(ll base, ll exp){
	if(exp == 0) return 1;
	if(exp == 1) return base;
	ll temp = POW(base, exp/2);
	temp = (temp*temp)%mod;
	if(exp%2 == 0) return temp;
	else return (base*temp)%mod;
}

ii query(int i, int s, int e, int l, int r){
	if(s >= l && e <= r){
		return t[i];
	}
	if(s > r || e < l) return {0, 0};
	int m = (s + e)>>1;
	return merge(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r));
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	a = vector<ll>(2*n-1);
	for(int i = 0; i < n; i++){
		ll t; cin>>t;
		a[n+i-1] = t;
		a[n-i-1] = t;
	}
	compress();
//	for(int i = 0; i < a.size(); i++){
//		cout<<a[i]<<" ";
//	}
	//cout<<endl;
	for(int i = 0; i < 4*LMAX; i++){
		t[i] = {0, 0};
	}
	for(int i = 0; i < a.size(); i++){
		auto qval = query(1, 0, unum, 0, a[i]-1);
		qval.first++;
		qval = merge(qval, {1, 1});
		upd(1, 0, unum, a[i], qval);
	}
	auto with_middle = query(1, 0, unum, 0, unum);
	//cout<<"WITH_MIDDLE "<<with_middle.first<<" "<<with_middle.second<<endl;
	for(int i = 0; i < 4*LMAX; i++){
		t[i] = {0, 0};
	}
	for(int i = 0; i < a.size(); i++){
		if(i == n-1) continue;
		auto qval = query(1, 0, unum, 0, a[i]-1);
		qval.first++;
		qval = merge(qval, {1, 1});
		upd(1, 0, unum, a[i], qval);
	}
	auto without_middle = query(1, 0, unum, 0, unum);
	//cout<<"WITHOUT_MIDDLE "<<without_middle.first<<" "<<without_middle.second<<endl;
	ll middle = 0;
	if(with_middle.first > without_middle.first){
		without_middle = {0, 0};
		middle = with_middle.second;
	}else if(without_middle.first == with_middle.first){
		middle = (with_middle.second - without_middle.second + mod)%mod;
	}else{
		middle = 0;
	}
	ll ans = (without_middle.second*POW(2, n-1-without_middle.first))%mod + (middle*POW(2, n-with_middle.first))%mod;
	cout<<max(with_middle.first, without_middle.first)<<" "<<ans<<endl;
}

Compilation message (stderr)

zoltan.cpp: In function 'void compress()':
zoltan.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~

• Subtask 1: 133 / 140