oj.uz

Submission #707825

# Submission time Handle Problem Language Result Execution time Memory
707825 2023-03-10T09:03:41 Z YugiHacker Zoltan (COCI16_zoltan) C++14
140 / 140
 98 ms 5960 KB 
/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 200005
#define pii pair<int,int>
#define fi first
#define se second
#define MOD 1000000007
using namespace std;
int n, a[maxn];
void operator += (pii &a, pii b)
{
    if (a.fi == b.fi) (a.se += b.se) %= MOD;
    else if (a.fi < b.fi) a = b;
}
struct Fenwick
{
    vector <pii> t;
    Fenwick(int n){
        t.resize(n+5);
    }
    pii getHigh(int x)
    {
        pii ans = {0, 1};
        for (;x<=n; x+=x&-x) ans += t[x];
        return ans;
    }
    void upLow(int x, pii val)
    {
        for (;x; x-=x&-x) t[x] += val;
    }

    pii getLow(int x)
    {
        pii ans = {0, 1};
        for (;x; x-=x&-x) ans += t[x];
        return ans;
    }
    void upHigh(int x, pii val)
    {
        for (;x<=n; x+=x&-x) t[x] += val;
    }
};
int p[maxn];
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    vector <int> v;
    p[0] = 1;
    f1 (i, n) cin >> a[i], v.push_back(a[i]), p[i] = p[i-1] * 2 % MOD;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    reverse(a+1, a+n+1);
    Fenwick BIT_inc(n), BIT_dec(n);
    pii ans = {0, 1};
    f1 (i, n)
    {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
        pii x = BIT_inc.getLow(a[i] - 1);
        pii y = BIT_dec.getHigh(a[i] + 1);
        ++x.fi; ++y.fi;
        pii cur = {x.fi + y.fi - 1, 1ll * x.se * y.se % MOD};
        ans += cur;
        BIT_inc.upHigh(a[i], x);
        BIT_dec.upLow(a[i], y);
    }
    cout << ans.fi << ' ' << 1ll * ans.se * p[n - ans.fi] % MOD;
}

Compilation message

zoltan.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 51 ms 4716 KB Output is correct
12 Correct 45 ms 4256 KB Output is correct
13 Correct 41 ms 3924 KB Output is correct
14 Correct 64 ms 4176 KB Output is correct
15 Correct 82 ms 5064 KB Output is correct
16 Correct 98 ms 5864 KB Output is correct
17 Correct 69 ms 5844 KB Output is correct
18 Correct 69 ms 5960 KB Output is correct
19 Correct 63 ms 5932 KB Output is correct
20 Correct 64 ms 5940 KB Output is correct