oj.uz

Submission #973551

# Submission time Handle Problem Language Result Execution time Memory
973551 2024-05-02T07:06:26 Z vjudge1 Zoltan (COCI16_zoltan) C++17
70 / 140
 179 ms 35588 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[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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4188 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4188 KB Output is correct
7 Correct 2 ms 4052 KB Output is correct
8 Correct 2 ms 4184 KB Output is correct
9 Correct 2 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Runtime error 83 ms 29768 KB Execution killed with signal 11
12 Runtime error 74 ms 26964 KB Execution killed with signal 11
13 Runtime error 72 ms 25732 KB Execution killed with signal 11
14 Runtime error 96 ms 27216 KB Execution killed with signal 11
15 Runtime error 122 ms 31824 KB Execution killed with signal 11
16 Runtime error 179 ms 35588 KB Execution killed with signal 11
17 Runtime error 78 ms 31028 KB Execution killed with signal 11
18 Runtime error 82 ms 30800 KB Execution killed with signal 11
19 Runtime error 80 ms 30952 KB Execution killed with signal 11
20 Runtime error 78 ms 30940 KB Execution killed with signal 11