Submission #52048

#TimeUsernameProblemLanguageResultExecution timeMemory
52048Adhyyan1252Zoltan (COCI16_zoltan)C++11
126 / 140
1087 ms19964 KiB
#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(); unum+=2; // 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 (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:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
zoltan.cpp:100:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...