oj.uz

답안 #856523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856523 2023-10-03T18:55:34 Z ArminAzimi Zoltan (COCI16_zoltan) C++14
21 / 140
 220 ms 27356 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 = 2e5 + 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());
    kol.resize(unique(kol.begin(), kol.end()) - kol.begin());

    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
21.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 14936 KB Output isn't correct
2 Incorrect 3 ms 14940 KB Output isn't correct
3 Incorrect 4 ms 14940 KB Output isn't correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14936 KB Output is correct
6 Correct 2 ms 14936 KB Output is correct
7 Incorrect 3 ms 14940 KB Output isn't correct
8 Incorrect 3 ms 15192 KB Output isn't correct
9 Incorrect 4 ms 14940 KB Output isn't correct
10 Incorrect 3 ms 15060 KB Output isn't correct
11 Incorrect 144 ms 25288 KB Output isn't correct
12 Incorrect 124 ms 23504 KB Output isn't correct
13 Incorrect 124 ms 21156 KB Output isn't correct
14 Incorrect 147 ms 21968 KB Output isn't correct
15 Incorrect 188 ms 23760 KB Output isn't correct
16 Incorrect 220 ms 25468 KB Output isn't correct
17 Incorrect 193 ms 27356 KB Output isn't correct
18 Incorrect 194 ms 27332 KB Output isn't correct
19 Incorrect 192 ms 27320 KB Output isn't correct
20 Incorrect 195 ms 27340 KB Output isn't correct