oj.uz

답안 #856511

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856511 2023-10-03T18:36:37 Z ArminAzimi Zoltan (COCI16_zoltan) C++14
0 / 140
 187 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair <int, int>, null_type,less<pair <int, int>>, rb_tree_tag,tree_order_statistics_node_update> 

const int MAXN = 1e6 + 10, MAXM = 1e2 + 10, MOD = 1000000000 + 7, MOD1 = 1e9 + 9, SQ = 350;
const long long INF = 1e9 + 11;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[MAXN], seg[4 * MAXN][2], dp[MAXN][2], cnt[MAXN][2], fen[MAXN][2], p2[MAXN];
vector <int> vec[MAXN][2];

void upd(int l, int r, int id, int ind, int val, int index) {
    if (l == r) {
        seg[id][index] = val;
        return;
    }

    int mid = (l + r) / 2;
    if (ind <= mid)
        upd(l, mid, 2 * id, ind, val, index);
    else
        upd(mid + 1, r, 2 * id + 1, ind, val, index);

    seg[id][index] = max(seg[2 * id][index], seg[2 * id + 1][index]);
}

int get(int l, int r, int id, int l1, int r1, int index) {
    if (r < l1 || r1 < l)
        return 0;
    if (l1 <= l && r <= r1)
        return seg[id][index];

    int mid = (l + r) / 2;
    return max(get(l, mid, 2 * id, l1, r1, index), get(mid + 1, r, 2 * id + 1, l1, r1, index));
}

void upd(int x, int val, int ind) {
    x++;
    for (; x < MAXN; x += x & (-x))
        fen[x][ind] = (fen[x][ind] + val) % MOD;
}

int get(int x, int ind) {
    int res = 0;
    for (; x; x -= x & (-x))
        res = (res + fen[x][ind]) % MOD;
    return res;
}

int get(int l, int r, int ind) {
    l++;
    r++;
    return ((get(r, ind) - get(l - 1, ind)) % MOD + MOD) % MOD;
}

void solve() {
    int n;
    cin >> n;

    vector <int> kol;
    p2[0] = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p2[i + 1] = 1ll * p2[i] * 2 % MOD;
        kol.push_back(a[i]);
    }

    sort(kol.begin(), kol.end());

    for (int i = 0; i < n; i++)
        a[i] = lower_bound(kol.begin(), kol.end(), a[i]) - kol.begin();
    
    for (int i = n - 1; i >= 0; i--) {
        dp[i][0] = get(0, n, 1, a[i] + 1, n, 0) + 1;
        dp[i][1] = get(0, n, 1, 0, a[i] - 1, 1) + 1;

        upd(0, n, 1, a[i], dp[i][0], 0);
        upd(0, n, 1, a[i], dp[i][1], 1);
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i][0] + dp[i][1] - 1);
        vec[dp[i][0]][0].push_back(i);
        vec[dp[i][1]][1].push_back(i);

        if (dp[i][0] == 1)
            cnt[i][0] = 1;
        if (dp[i][1] == 1)
            cnt[i][1] = 1;
    }

    for (int i = 1; i < ans; i++) {
        for (int ind: vec[i][0])
            upd(a[ind], cnt[ind][0], 0);
        for (int ind: vec[i][1])
            upd(a[ind], cnt[ind][1], 1);

        // cout << i << " = ";
        // for (int i = 0; i < n; i++)
        //     cout << get(i, i, 0) << " ";
        // cout << "\n";

        for (int ind: vec[i + 1][0])
            cnt[ind][0] = get(a[ind] + 1, n, 0);
        for (int ind: vec[i + 1][1])
            cnt[ind][1] = get(0, a[ind] - 1, 1);
        
        for (int ind: vec[i][0])
            upd(a[ind], -cnt[ind][0], 0);
        for (int ind: vec[i][1])
            upd(a[ind], -cnt[ind][1], 1);
        
    }

    int ans1 = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i][0] + dp[i][1] - 1 == ans) {
            int tmp = 1ll * cnt[i][0] * cnt[i][1] % MOD;
            tmp = 1ll * tmp * p2[n - ans] % MOD;

            ans1 = (ans1 + tmp) % MOD;
        }
    }

    cout << ans << " " << ans1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    // cin >> q;
    
    while (q--) {
        solve();
    }
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 53852 KB Memory limit exceeded
2 Runtime error 10 ms 54056 KB Memory limit exceeded
3 Runtime error 11 ms 53852 KB Memory limit exceeded
4 Runtime error 11 ms 54108 KB Memory limit exceeded
5 Runtime error 11 ms 53852 KB Memory limit exceeded
6 Runtime error 10 ms 53852 KB Memory limit exceeded
7 Runtime error 12 ms 54020 KB Memory limit exceeded
8 Runtime error 11 ms 53848 KB Memory limit exceeded
9 Runtime error 12 ms 53852 KB Memory limit exceeded
10 Runtime error 12 ms 53852 KB Memory limit exceeded
11 Runtime error 130 ms 65536 KB Execution killed with signal 9
12 Runtime error 136 ms 65492 KB Memory limit exceeded
13 Runtime error 127 ms 64972 KB Memory limit exceeded
14 Runtime error 156 ms 65484 KB Memory limit exceeded
15 Runtime error 155 ms 65536 KB Execution killed with signal 9
16 Runtime error 187 ms 65536 KB Execution killed with signal 9
17 Runtime error 155 ms 65536 KB Execution killed with signal 9
18 Runtime error 165 ms 65536 KB Execution killed with signal 9
19 Runtime error 160 ms 65536 KB Execution killed with signal 9
20 Runtime error 151 ms 65536 KB Execution killed with signal 9