/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 2.02 MiB
#2 Accepted 4ms 1.84 MiB
#3 Accepted 4ms 2.023 MiB
#4 Accepted 5ms 2.066 MiB
#5 Accepted 8ms 2.02 MiB
#6 Accepted 8ms 2.02 MiB
#7 Accepted 8ms 2.074 MiB
#8 Accepted 8ms 2.02 MiB
#9 Accepted 8ms 2.023 MiB
#10 Accepted 8ms 2.02 MiB
#11 Accepted 8ms 2.02 MiB
#12 Accepted 8ms 1.84 MiB
#13 Accepted 10ms 2.02 MiB
#14 Accepted 11ms 1.887 MiB
#15 Accepted 11ms 2.02 MiB
#16 Accepted 11ms 1.918 MiB
#17 Accepted 11ms 2.078 MiB
#18 Accepted 11ms 2.02 MiB
#19 Accepted 11ms 1.859 MiB
#20 Accepted 11ms 2.02 MiB
#21 Accepted 11ms 1.836 MiB
#22 Accepted 11ms 2.02 MiB
#23 Accepted 11ms 2.02 MiB
#24 Accepted 11ms 2.02 MiB
#25 Accepted 11ms 2.02 MiB
#26 Accepted 11ms 2.078 MiB
#27 Accepted 11ms 2.02 MiB
#28 Accepted 11ms 1.969 MiB
#29 Accepted 12ms 1.891 MiB
#30 Accepted 11ms 2.066 MiB
#31 Accepted 6ms 2.02 MiB
#32 Accepted 6ms 2.059 MiB
#33 Accepted 6ms 2.02 MiB
#34 Accepted 6ms 2.082 MiB
#35 Accepted 6ms 2.02 MiB
#36 Accepted 6ms 2.02 MiB
#37 Accepted 6ms 2.02 MiB
#38 Accepted 6ms 2.02 MiB
#39 Accepted 6ms 2.02 MiB
#40 Accepted 6ms 1.988 MiB
#41 Accepted 7ms 2.062 MiB
#42 Accepted 7ms 2.066 MiB
#43 Accepted 7ms 1.984 MiB
#44 Accepted 7ms 2.02 MiB
#45 Accepted 7ms 2.02 MiB
#46 Accepted 7ms 2.02 MiB
#47 Accepted 7ms 2.246 MiB
#48 Accepted 9ms 2.02 MiB
#49 Accepted 9ms 1.832 MiB
#50 Accepted 11ms 2.062 MiB
#51 Accepted 11ms 2.02 MiB
#52 Accepted 11ms 2.062 MiB
#53 Accepted 11ms 1.953 MiB
#54 Accepted 11ms 2.02 MiB
#55 Accepted 11ms 1.973 MiB
#56 Accepted 11ms 2.0 MiB
#57 Accepted 11ms 2.02 MiB
#58 Accepted 11ms 2.02 MiB
#59 Accepted 11ms 2.043 MiB
#60 Accepted 11ms 1.84 MiB
#61 Accepted 11ms 1.836 MiB
#62 Accepted 11ms 2.02 MiB
#63 Accepted 11ms 1.836 MiB
#64 Accepted 11ms 2.02 MiB
#65 Accepted 11ms 1.938 MiB
#66 Accepted 11ms 1.836 MiB
#67 Accepted 11ms 2.02 MiB
#68 Accepted 11ms 2.062 MiB
#69 Accepted 11ms 2.02 MiB
#70 Accepted 11ms 2.02 MiB
#71 Accepted 11ms 2.023 MiB
#72 Accepted 11ms 2.062 MiB
#73 Accepted 11ms 2.016 MiB
#74 Accepted 11ms 2.02 MiB
#75 Accepted 11ms 2.066 MiB
#76 Accepted 11ms 2.066 MiB
#77 Accepted 11ms 2.02 MiB
#78 Accepted 11ms 2.02 MiB
#79 Accepted 11ms 1.969 MiB
#80 Accepted 11ms 2.02 MiB
#81 Accepted 11ms 2.02 MiB
#82 Accepted 11ms 1.973 MiB
#83 Accepted 11ms 2.02 MiB
#84 Accepted 11ms 2.02 MiB
#85 Accepted 11ms 1.891 MiB
#86 Accepted 11ms 2.043 MiB
#87 Accepted 11ms 2.02 MiB
#88 Accepted 11ms 2.02 MiB
#89 Accepted 11ms 2.02 MiB
#90 Accepted 13ms 2.031 MiB
#91 Accepted 11ms 2.023 MiB
#92 Accepted 61ms 5.848 MiB
#93 Accepted 42ms 5.852 MiB
#94 Accepted 39ms 5.844 MiB
#95 Accepted 39ms 5.77 MiB
#96 Accepted 43ms 5.855 MiB
#97 Accepted 40ms 5.816 MiB
#98 Accepted 41ms 5.77 MiB
#99 Accepted 42ms 5.777 MiB
#100 Accepted 40ms 5.848 MiB

Code

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int MAXN = 200000;

vector<long long> pow2;

struct Fenwick {
    vector<int> bit;
    int n;
    Fenwick(int n) : n(n), bit(n+1, 0) {}
    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] += val;
    }
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx)
            sum += bit[idx];
        return sum;
    }
};

void precompute_pow2() {
    pow2.resize(MAXN + 5);
    pow2[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        pow2[i] = (pow2[i-1] * 2) % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute_pow2();

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int i = 0; i < N; i++) cin >> A[i];

        vector<int> leftCount(N), rightCount(N);

        // --- Left Count ---
        Fenwick BITleft(N);
        for (int i = 0; i < N; i++) {
            int val = A[i];
            leftCount[i] = BITleft.query(val - 1);
            BITleft.update(val, 1);
        }

        // --- Right Count ---
        Fenwick BITright(N);
        for (int i = N - 1; i >= 0; i--) {
            int val = A[i];
            rightCount[i] = BITright.query(val - 1);
            BITright.update(val, 1);
        }

        long long ans = 0;
        for (int i = 1; i < N - 1; i++) {
            long long L = leftCount[i];
            long long R = rightCount[i];

            if (L > 0 && R > 0) {
                long long waysL = (pow2[L] - 1 + MOD) % MOD;
                long long waysR = (pow2[R] - 1 + MOD) % MOD;
                ans = (ans + (waysL * waysR) % MOD) % MOD;
            }
        }

        cout << ans << "\n";
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1213 good sequence
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-26 23:22:51
Judged At
2025-07-26 23:22:51
Judged By
Score
100
Total Time
61ms
Peak Memory
5.855 MiB