oj.uz

답안 #52047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52047 2018-06-23T11:02:27 Z Adhyyan1252 Zoltan (COCI16_zoltan) C++11
126 / 140
 1000 ms 20012 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<int> 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, const ii &b){
	if(a.first > b.first){
		return a;
	}else if(b.first > a.first){
		return b;
	}else{
		a.second = (a.second + b.second);
		if(a.second >= mod) a.second -= mod;
		return a;
	}
}
#define SLEN 534288
ii t[SLEN];
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<int>(2*n-1);
	for(int i = 0; i < n; i++){
		int 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 < SLEN; 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 < SLEN; 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;
	}
	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:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp:99:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~

Subtask #1
126.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8696 KB Output is correct
2 Correct 12 ms 8696 KB Output is correct
3 Correct 10 ms 8752 KB Output is correct
4 Correct 10 ms 8768 KB Output is correct
5 Correct 9 ms 8768 KB Output is correct
6 Correct 10 ms 8828 KB Output is correct
7 Correct 10 ms 8828 KB Output is correct
8 Incorrect 13 ms 8828 KB Output isn't correct
9 Correct 10 ms 8956 KB Output is correct
10 Correct 10 ms 8972 KB Output is correct
11 Correct 425 ms 17728 KB Output is correct
12 Correct 377 ms 17728 KB Output is correct
13 Correct 408 ms 17728 KB Output is correct
14 Correct 629 ms 17728 KB Output is correct
15 Correct 893 ms 18472 KB Output is correct
16 Execution timed out 1046 ms 20012 KB Time limit exceeded
17 Correct 556 ms 20012 KB Output is correct
18 Correct 543 ms 20012 KB Output is correct
19 Correct 674 ms 20012 KB Output is correct
20 Correct 533 ms 20012 KB Output is correct