oj.uz

답안 #856510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856510 2023-10-03T18:31:55 Z ArminAzimi Zoltan (COCI16_zoltan) C++14
0 / 140
 207 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;
}

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 11 ms 53852 KB Memory limit exceeded
2 Runtime error 11 ms 53852 KB Memory limit exceeded
3 Runtime error 11 ms 53888 KB Memory limit exceeded
4 Runtime error 11 ms 53984 KB Memory limit exceeded
5 Runtime error 11 ms 53920 KB Memory limit exceeded
6 Runtime error 11 ms 53976 KB Memory limit exceeded
7 Runtime error 12 ms 53992 KB Memory limit exceeded
8 Runtime error 13 ms 54108 KB Memory limit exceeded
9 Runtime error 12 ms 53916 KB Memory limit exceeded
10 Runtime error 13 ms 54104 KB Memory limit exceeded
11 Runtime error 131 ms 65536 KB Execution killed with signal 9
12 Runtime error 135 ms 65536 KB Memory limit exceeded
13 Runtime error 127 ms 65536 KB Memory limit exceeded
14 Runtime error 169 ms 65200 KB Memory limit exceeded
15 Runtime error 197 ms 65536 KB Memory limit exceeded
16 Runtime error 207 ms 65536 KB Execution killed with signal 9
17 Runtime error 155 ms 65536 KB Execution killed with signal 9
18 Runtime error 154 ms 65536 KB Execution killed with signal 9
19 Runtime error 155 ms 65536 KB Execution killed with signal 9
20 Runtime error 159 ms 65536 KB Execution killed with signal 9