oj.uz

Submission #707824

# Submission time Handle Problem Language Result Execution time Memory
707824 2023-03-10T09:00:50 Z YugiHacker Zoltan (COCI16_zoltan) C++14
0 / 140
 39 ms 11948 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];
pii 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: In function 'std::pair<int, int> operator+=(std::pair<int, int>&, std::pair<int, int>)':
zoltan.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
   20 | }
      | ^
zoltan.cpp: At global scope:
zoltan.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Runtime error 1 ms 468 KB Execution killed with signal 11
4 Runtime error 1 ms 468 KB Execution killed with signal 11
5 Runtime error 1 ms 468 KB Execution killed with signal 11
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11
9 Runtime error 1 ms 468 KB Execution killed with signal 11
10 Runtime error 1 ms 468 KB Execution killed with signal 11
11 Runtime error 24 ms 9496 KB Execution killed with signal 11
12 Runtime error 24 ms 8264 KB Execution killed with signal 11
13 Runtime error 21 ms 7928 KB Execution killed with signal 11
14 Runtime error 27 ms 8352 KB Execution killed with signal 11
15 Runtime error 32 ms 10240 KB Execution killed with signal 11
16 Runtime error 39 ms 11776 KB Execution killed with signal 11
17 Runtime error 34 ms 11840 KB Execution killed with signal 11
18 Runtime error 33 ms 11812 KB Execution killed with signal 11
19 Runtime error 34 ms 11844 KB Execution killed with signal 11
20 Runtime error 35 ms 11948 KB Execution killed with signal 11