oj.uz

답안 #229995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229995 2020-05-07T14:53:33 Z osaaateiasavtnl Zoltan (COCI16_zoltan) C++14
21 / 140
 342 ms 29676 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7, MOD = 1000 * 1000 * 1000 + 7;
int a[N], l[N], r[N], cntl[N], cntr[N], pw[N];

struct Seg {

ii tree[N << 2];
ii merge(ii a, ii b) {
    if (a.f > b.f)
        return a;
    if (b.f > a.f)
        return b;
    return mp(a.f, (a.s + b.s) % MOD);
}   
void add(int v, int l, int r, int i, ii e) {
    if (l == r) {
        tree[v] = merge(tree[v], e);
        return;
    }   
    int m = (l + r) >> 1;
    if (i <= m)
        add(v * 2 + 1, l, m, i, e);
    else
        add(v * 2 + 2, m + 1, r, i, e);
    tree[v] = merge(tree[v * 2 + 1], tree[v * 2 + 2]);                   
}   
ii get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return mp(0, 0);
    if (l <= tl && tr <= r)
        return tree[v];            
    int m = (tl + tr) >> 1;
    return merge(get(v * 2 + 1, tl, m, l, r), get(v * 2 + 2, m + 1, tr, l, r));
}   

} L, R;  

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = (pw[i - 1] * 2) % MOD;

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector <int> c;
    for (int i = 0; i < n; ++i)
        c.app(a[i]);
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(all(c), a[i]) - c.begin();

    int len = 0;
    for (int i = n; i; --i) {
        tie(l[i], cntl[i]) = L.get(0, 0, N, 0, a[i] - 1);
        ++l[i];
        if (l[i] == 1)
            cntl[i] = 1;

        tie(r[i], cntr[i]) = R.get(0, 0, N, a[i] + 1, N);
        ++r[i];
        if (r[i] == 1)
            cntr[i] = 1;
        
        L.add(0, 0, N, a[i], mp(l[i], cntl[i]));
        R.add(0, 0, N, a[i], mp(r[i], cntr[i]));
        len = max(len, l[i] + r[i] - 1);
    }   

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (l[i] + r[i] - 1 == len) {
            ans += (cntl[i] * cntr[i]) % MOD;
            ans %= MOD;
        }   
    }
    ans = ans * pw[n - len] % MOD;

    cout << len << ' ' << ans << endl;
}

Subtask #1
21.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2048 KB Output isn't correct
2 Incorrect 6 ms 2048 KB Output isn't correct
3 Incorrect 7 ms 2048 KB Output isn't correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 6 ms 2048 KB Output is correct
6 Correct 6 ms 1920 KB Output is correct
7 Incorrect 7 ms 2304 KB Output isn't correct
8 Incorrect 7 ms 2304 KB Output isn't correct
9 Incorrect 7 ms 2304 KB Output isn't correct
10 Incorrect 7 ms 2176 KB Output isn't correct
11 Incorrect 186 ms 23784 KB Output isn't correct
12 Incorrect 150 ms 20840 KB Output isn't correct
13 Incorrect 149 ms 19824 KB Output isn't correct
14 Incorrect 221 ms 21348 KB Output isn't correct
15 Incorrect 283 ms 26088 KB Output isn't correct
16 Incorrect 342 ms 29676 KB Output isn't correct
17 Incorrect 217 ms 26476 KB Output isn't correct
18 Incorrect 229 ms 26472 KB Output isn't correct
19 Incorrect 217 ms 26600 KB Output isn't correct
20 Incorrect 225 ms 26600 KB Output isn't correct