Submission #973551

#	Time	Username	Problem	Language	Result	Execution time	Memory
973551		vjudge1	Zoltan (COCI16_zoltan)	C++17	70 / 140	179 ms	35588 KiB

zoltan

#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[100100],T2[100100];
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[100100];
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();
}

• Subtask 1: 70 / 140