Submission #1307119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307119		Taxiradio	Bubble Sort Machine (JOI25_bubble)	C++20	100 / 100	891 ms	74900 KiB

bubble

#include<bits/stdc++.h>

using namespace std;

#define int int64_t

int f[600000] , f2[600000];

void add(int p , int v){
    while(p < 600000){
        f[p]+=v;
        p +=(-p)&p;
    }
}

int get(int p){
    int ans = 0;
    while(p>0){
        ans += f[p];
        p -= (-p)&p;
    }
    return ans;
}

void add2(int p , int v){
    while(p < 600000){
        f2[p]+=v;
        p +=(-p)&p;
    }
}

int get2(int p){
    int ans = 0;
    while(p>0){
        ans += f2[p];
        p -= (-p)&p;
    }
    return ans;
}


int32_t main(){
    int n; cin >> n;
    vector<array<int , 2>> a , c(n);
    vector<int> p;p.push_back(0);
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        a.push_back({x , i});
        p.push_back(p.back()+x);
    }
    sort(a.begin() , a.end());
    for(int i = 0; i < n; i++){
        c[a[i][1]] = {a[i][0] , i};
    }
    int q;cin >> q;
    int u = 0;
    vector<array<int , 4>> o;
    vector<int> ans;
    while(q--){
        int b; cin >> b;
        if(b==1){
            u++;
            continue;
        }
        int l , r; cin >> l >> r;
        o.push_back({min(l-1+u , n)-1  , min(l-1+u , n)-(l-1) , int(ans.size()) , 1});
        o.push_back({min(r+u , n)-1  , min(r+u , n)-(r) , int(ans.size()) , -1});
        int h = 0;
        h += p[r]-p[l-1];
        h -= p[min(l+u-1 , n)]-p[l-1];
        h += p[min(r+u , n)]-p[r];
        ans.push_back(h);
    }
    sort(o.begin() , o.end());
    int j = -1;
    for(int i = 0; i < o.size(); i++){
        while(j < o[i][0]){
            j++;
            add(n-c[j][1] , c[j][0]);
            add2(n-c[j][1] , 1);
        }
        int l = 0 , r = 600000;
        while(l+1 != r){
            int m = (l+r)/2;
            if(get2(m) > o[i][1])r=m; else l=m;
        }
        ans[o[i][2]] += o[i][3]*get(l);
    }
    for(int x : ans) cout << x << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 29 / 29
• Subtask 6: 17 / 17