oj.uz

Submission #52036

# Submission time Handle Problem Language Result Execution time Memory
52036 2018-06-23T10:43:44 Z Adhyyan1252 Zoltan (COCI16_zoltan) C++11
0 / 140
 1000 ms 40060 KB 
#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(){
	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

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:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 12868 KB Output isn't correct
2 Incorrect 17 ms 13040 KB Output isn't correct
3 Incorrect 16 ms 13040 KB Output isn't correct
4 Incorrect 15 ms 13040 KB Output isn't correct
5 Incorrect 16 ms 13040 KB Output isn't correct
6 Incorrect 15 ms 13108 KB Output isn't correct
7 Incorrect 18 ms 13108 KB Output isn't correct
8 Incorrect 18 ms 13156 KB Output isn't correct
9 Incorrect 17 ms 13184 KB Output isn't correct
10 Incorrect 17 ms 13260 KB Output isn't correct
11 Incorrect 747 ms 26196 KB Output isn't correct
12 Incorrect 611 ms 26196 KB Output isn't correct
13 Incorrect 577 ms 26196 KB Output isn't correct
14 Incorrect 999 ms 28076 KB Output isn't correct
15 Execution timed out 1062 ms 32320 KB Time limit exceeded
16 Execution timed out 1083 ms 36672 KB Time limit exceeded
17 Incorrect 916 ms 36672 KB Output isn't correct
18 Incorrect 927 ms 37412 KB Output isn't correct
19 Incorrect 942 ms 38928 KB Output isn't correct
20 Incorrect 875 ms 40060 KB Output isn't correct