oj.uz

Submission #707822

# Submission time Handle Problem Language Result Execution time Memory
707822 2023-03-10T08:59:50 Z YugiHacker Zoltan (COCI16_zoltan) C++14
0 / 140
 40 ms 13700 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;
    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 460 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 25 ms 10700 KB Execution killed with signal 11
12 Runtime error 22 ms 9376 KB Execution killed with signal 11
13 Runtime error 21 ms 8908 KB Execution killed with signal 11
14 Runtime error 29 ms 9672 KB Execution killed with signal 11
15 Runtime error 40 ms 11936 KB Execution killed with signal 11
16 Runtime error 40 ms 13700 KB Execution killed with signal 11
17 Runtime error 34 ms 13068 KB Execution killed with signal 11
18 Runtime error 34 ms 13096 KB Execution killed with signal 11
19 Runtime error 34 ms 13024 KB Execution killed with signal 11
20 Runtime error 34 ms 13032 KB Execution killed with signal 11