# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
973552 | vjudge1 | Zoltan (COCI16_zoltan) | C++17 | 185 ms | 20560 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod=1e9+7,CC;
struct info{
int val,way;
info(){val=0,way=0;}
info operator+=(info b){
if(b.val>val)
*this=b;
else if(b.val==val)
way=(way+b.way)%mod;
return *this;
}
void print(){
cout<<val<<' '<<way<<'\n';
}
}T1[200100],T2[200100];
info query(int x,info T[]){
info b=info();
b.way++;
for(;x;x-=x&-x)
b+=T[x];
return b;
}
void update(int x,info T[],info upd){
for(;x<=CC;x+=x&-x)
T[x]+=upd;
}
int arr[200100];
map<int,int>mp;
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i],mp[arr[i]];
reverse(arr,arr+n);
for(auto&[i,j]:mp)
j=++CC;
for(int i=0;i<n;i++)
arr[i]=mp[arr[i]];
info ans=info();
for(int i=0;i<n;i++){
info a1=query(arr[i]-1,T1),a2=query(CC-arr[i],T2);
a1.val++,a2.val++; info c;
c.val=a1.val+a2.val-1;
c.way=a1.way*a2.way%mod,ans+=c;
update(arr[i],T1,a1),update(CC+1-arr[i],T2,a2);
}
for(int i=0;i<n-ans.val;i++)
ans.way=ans.way*2%mod;
ans.print();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |