oj.uz

Submission #973552

# Submission time Handle Problem Language Result Execution time Memory
973552 2024-05-02T07:06:47 Z vjudge1 Zoltan (COCI16_zoltan) C++17
140 / 140
 185 ms 20560 KB 
#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();
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 98 ms 18068 KB Output is correct
12 Correct 92 ms 16848 KB Output is correct
13 Correct 81 ms 16356 KB Output is correct
14 Correct 110 ms 16720 KB Output is correct
15 Correct 150 ms 18864 KB Output is correct
16 Correct 185 ms 20560 KB Output is correct
17 Correct 99 ms 18996 KB Output is correct
18 Correct 96 ms 18732 KB Output is correct
19 Correct 96 ms 18740 KB Output is correct
20 Correct 95 ms 18512 KB Output is correct