/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 4ms 440.0 KiB
#3 Accepted 5ms 532.0 KiB
#4 Accepted 5ms 532.0 KiB
#5 Accepted 5ms 508.0 KiB
#6 Accepted 5ms 532.0 KiB
#7 Accepted 5ms 576.0 KiB
#8 Accepted 5ms 532.0 KiB
#9 Accepted 5ms 532.0 KiB
#10 Accepted 5ms 532.0 KiB
#11 Accepted 5ms 532.0 KiB
#12 Accepted 5ms 536.0 KiB
#13 Accepted 5ms 532.0 KiB
#14 Accepted 5ms 532.0 KiB
#15 Accepted 5ms 580.0 KiB
#16 Accepted 5ms 532.0 KiB
#17 Accepted 5ms 532.0 KiB
#18 Accepted 5ms 532.0 KiB
#19 Accepted 5ms 532.0 KiB
#20 Accepted 5ms 532.0 KiB
#21 Accepted 5ms 532.0 KiB
#22 Accepted 5ms 532.0 KiB
#23 Accepted 5ms 532.0 KiB
#24 Accepted 5ms 532.0 KiB
#25 Accepted 5ms 532.0 KiB
#26 Accepted 5ms 444.0 KiB
#27 Accepted 5ms 444.0 KiB
#28 Accepted 5ms 532.0 KiB
#29 Accepted 5ms 532.0 KiB
#30 Accepted 5ms 532.0 KiB
#31 Accepted 5ms 532.0 KiB
#32 Accepted 5ms 532.0 KiB
#33 Accepted 5ms 532.0 KiB
#34 Accepted 5ms 532.0 KiB
#35 Accepted 5ms 788.0 KiB
#36 Accepted 5ms 532.0 KiB
#37 Accepted 5ms 532.0 KiB
#38 Accepted 5ms 532.0 KiB
#39 Accepted 5ms 532.0 KiB
#40 Accepted 5ms 532.0 KiB
#41 Accepted 5ms 532.0 KiB
#42 Accepted 5ms 488.0 KiB
#43 Accepted 5ms 532.0 KiB
#44 Accepted 5ms 348.0 KiB
#45 Accepted 5ms 532.0 KiB
#46 Accepted 5ms 576.0 KiB
#47 Accepted 5ms 348.0 KiB
#48 Accepted 5ms 540.0 KiB
#49 Accepted 5ms 488.0 KiB
#50 Accepted 5ms 532.0 KiB
#51 Accepted 5ms 484.0 KiB
#52 Accepted 5ms 532.0 KiB
#53 Accepted 5ms 532.0 KiB
#54 Accepted 5ms 532.0 KiB
#55 Accepted 5ms 580.0 KiB
#56 Accepted 5ms 532.0 KiB
#57 Accepted 5ms 324.0 KiB
#58 Accepted 5ms 484.0 KiB
#59 Accepted 5ms 576.0 KiB
#60 Accepted 5ms 532.0 KiB
#61 Accepted 5ms 532.0 KiB
#62 Accepted 5ms 532.0 KiB
#63 Accepted 5ms 532.0 KiB
#64 Accepted 5ms 580.0 KiB
#65 Accepted 5ms 536.0 KiB
#66 Accepted 5ms 532.0 KiB
#67 Accepted 5ms 532.0 KiB
#68 Accepted 5ms 576.0 KiB
#69 Accepted 5ms 532.0 KiB
#70 Accepted 5ms 320.0 KiB
#71 Accepted 5ms 532.0 KiB
#72 Accepted 5ms 532.0 KiB
#73 Accepted 5ms 532.0 KiB
#74 Accepted 5ms 344.0 KiB
#75 Accepted 5ms 532.0 KiB
#76 Accepted 5ms 516.0 KiB
#77 Accepted 5ms 532.0 KiB
#78 Accepted 5ms 532.0 KiB
#79 Accepted 5ms 488.0 KiB
#80 Accepted 5ms 532.0 KiB
#81 Accepted 5ms 532.0 KiB
#82 Accepted 5ms 568.0 KiB
#83 Accepted 5ms 532.0 KiB
#84 Accepted 5ms 532.0 KiB
#85 Accepted 5ms 532.0 KiB
#86 Accepted 5ms 532.0 KiB
#87 Accepted 5ms 532.0 KiB
#88 Accepted 5ms 544.0 KiB
#89 Accepted 5ms 576.0 KiB
#90 Accepted 5ms 576.0 KiB
#91 Accepted 5ms 532.0 KiB
#92 Accepted 214ms 5.324 MiB
#93 Accepted 213ms 5.09 MiB
#94 Accepted 210ms 5.238 MiB
#95 Accepted 219ms 5.324 MiB
#96 Accepted 212ms 5.332 MiB
#97 Accepted 219ms 5.34 MiB
#98 Accepted 212ms 5.336 MiB
#99 Accepted 215ms 5.328 MiB
#100 Accepted 213ms 5.27 MiB

Code

/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 2e5;
const ll mod = 1e9+7;
int a[N+2],sg1[N*4+10],sg2[N*4+10];

void build(int node,int start,int end)
{
    sg1[node] = 0;
    sg2[node] = 0;
    if(start == end) return;
    int mid = (start+end)>>1;
    build(node*2,start,mid);
    build(node*2+1,mid+1,end);
}

void update1(int node,int start,int end,int ind,int val)
{
    if(start==end)
    {
        sg1[node] += val;
        return;
    }
    int mid = (start+end)>>1;
    if(ind<=mid) update1(node*2,start,mid,ind,val);
    else update1(node*2+1,mid+1,end,ind,val);
    sg1[node] = sg1[node*2] + sg1[node*2+1];
}

void update2(int node,int start,int end,int ind,int val)
{
    if(start==end)
    {
        sg2[node] += val;
        return;
    }
    int mid = (start+end)>>1;
    if(ind<=mid) update2(node*2,start,mid,ind,val);
    else update2(node*2+1,mid+1,end,ind,val);
    sg2[node] = sg2[node*2] + sg2[node*2+1];
}

int query1(int node,int start,int end,int l,int r)
{
    if(l>end || r<start) return 0;
    if(l<=start && r>=end) return sg1[node];
    int mid = (start+end)>>1;
    return query1(node*2,start,mid,l,r) + query1(node*2+1,mid+1,end,l,r); 
}

int query2(int node,int start,int end,int l,int r)
{
    if(l>end || r<start) return 0;
    if(l<=start && r>=end) return sg2[node];
    int mid = (start+end)>>1;
    return query2(node*2,start,mid,l,r) + query2(node*2+1,mid+1,end,l,r);
}

ll Pow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    ans += mod;
    ans %= mod;
    return ans;
}

void solve(int tc)
{
    // string outp = "output"+to_string(tc)+".txt";
    // string inp = "input"+to_string(tc)+".txt";
    // ofstream file(outp);
    // freopen(inp.c_str(),"r",stdin);

    int t; cin >> t; while(t--){

    int n; cin >> n;
    build(1,1,n);
    for(int i=0;i<n;++i)
    {
        cin >> a[i];
        update2(1,1,n,a[i],1);
    }
    ll ans = 0;
    for(int i=0;i<n;i++)
    {
        update2(1,1,n,a[i],-1);
        if(a[i]>1) ans += ( (Pow(2,query1(1,1,n,1,a[i]-1))-1)  * (Pow(2,query2(1,1,n,1,a[i]-1))-1)) % mod;
        ans %= mod;
        update1(1,1,n,a[i],1);
    }
    ans = (ans + mod) % mod;
    cout<<ans<<'\n';}
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //for(int i=0;i<100;i++) solve(i);
    solve(0);
}

Information

Submit By
Type
Submission
Problem
P1213 good sequence
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-26 15:53:33
Judged At
2025-07-26 15:53:33
Judged By
Score
100
Total Time
219ms
Peak Memory
5.34 MiB