Submission #883996

#	Time	Username	Problem	Language	Result	Execution time	Memory
883996		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9061 ms	3668 KiB

bubblesort2

#include<bits/stdc++.h>
#include <bubblesort2.h>
using namespace std;
const int N = 5e5;
vector <int> a;
vector <int> v2;
vector <int> x;
class fenwick{
    int fen[N];
    int n;
public:
    void init(int sz){
        n = sz;
        for(int i = 0;i < n;i++)fen[i] = 0;
    }
    void add(int pos){
        for(int i = pos;i < n;i|=(i + 1)){
            fen[i]++;
        }
    }
    int get(int pos){
        int r = 0;
        for(int i = pos;i >= 0;i&=(i + 1),i--){
            r+=fen[i];
        }
        return r;
    }
};
int p[N];
fenwick fen;
int cnt = 0;
vector <int> countScans(vector <int> v,vector <int> q1,vector <int> q2){
    int n = v.size();
    int q = q1.size();
    vector<int>ans;
    for(int i = 0;i < q;i++){
        v[q1[i]] = q2[i];
        fen.init(n);
        int ans2 = 0;
        for(int j = 0;j < n;j++)p[j] = j;
        sort(p,p + n,[&](int a,int b){
             if(v[a] == v[b])return a > b;
             return v[a] > v[b];
        });
        for(int i = 0;i < n;i++){
            ans2 = max(ans2,fen.get(p[i]));
            fen.add(p[i]);
        }
        ans.push_back(ans2);
        //cout<<ans2<<' ';
    }
    return ans;
}
/*int main(){
    int n,q;
    cin>>n>>q;
    for(int i = 0;i < n;i++){
        int b;
        cin>>b;
        a.push_back(b);
    }
    for(int i=  0;i < q;i++){
        int b,c;
        cin>>b>>c;
        v2.push_back(c);
        x.push_back(b);
    }
    countScans(a,x,v2);
    return 0;
}*/
/**
4 2
1 2 3 4
0 3
2 1
**/

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40