Submission #884123

# Submission time Handle Problem Language Result Execution time Memory
884123 2023-12-06T16:02:03 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
280 ms 27060 KB
#include<bits/stdc++.h>
#include <bubblesort2.h>
using namespace std;
const int N = 5e5;
const int M = 100;
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 >= 0;i&=(i + 1),i--){
            fen[i]++;
        }
    }
    int get(int pos){
        int r = 0;
        for(int i = pos;i < n;i|=(i + 1)){
            r+=fen[i];
        }
        return r;
    }
};
int fen2[N][M];
int n,q;
void add(int x,int y,int nr){
    //cout<<"add:"<<x<<' '<<y<<' '<<nr<<'\n';
    for(int i = x;i < n;i|=(i + 1)){
        for(int j = y;j >= 0;j&=(j + 1),j--){
            fen2[i][j]+=nr;
        }
    }
}
int get(int x,int y){
    //cout<<"get:"<<x<<' '<<y<<' ';
    int r = 0;
    for(int i = x;i >= 0;i&=(i + 1),i--){
        for(int j = y;j < M;j|=(j + 1)){
            r+=fen2[i][j];
        }
    }
    //cout<<r<<'\n';
    return r;
}
set <int> last[M];
int p[N];
fenwick fen;
int cnt = 0;
vector <int> countScans(vector <int> v,vector <int> q1,vector <int> q2){
    n = v.size();
    q = q1.size();
    bool ok = 0;
    for(int i = 0;i < q;i++){
        q2[i]--;
    }
    for(int i = 0;i < n;i++){
        v[i]--;
        if(v[i] >= 100)ok = 1;
        if(v[i] < 100)last[v[i]].insert(i);
    }
    vector<int>ans;
    if(ok){
        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<<' ';
        }
    }else{
        for(int i = 0;i < n;i++){
            add(i,v[i],1);
        }
        for(int i = 0;i < q;i++){
            add(q1[i],v[q1[i]],-1);
            last[v[q1[i]]].erase(q1[i]);
            v[q1[i]] = q2[i];
            last[v[q1[i]]].insert(q1[i]);
            add(q1[i],v[q1[i]],1);
            int ans2 = 0;
            /*for(int j = 0;j < n;j++){
                ans2 = max(ans2,get(j - 1,v[j] + 1));
            }*/
            for(int j = 0;j < M;j++){
                if(!last[j].empty()){
                    int x = *last[j].rbegin();
                    ans2 = max(ans2,get(x - 1,v[x] + 1));
                }
            }
            ans.push_back(ans2);
            //cout<<ans2<<'\n';
        }
    }
    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
**/
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 18 ms 16360 KB Output is correct
2 Correct 123 ms 21676 KB Output is correct
3 Correct 209 ms 26728 KB Output is correct
4 Correct 201 ms 26776 KB Output is correct
5 Correct 224 ms 27060 KB Output is correct
6 Correct 229 ms 26836 KB Output is correct
7 Correct 280 ms 26832 KB Output is correct
8 Correct 242 ms 26828 KB Output is correct
9 Correct 222 ms 26836 KB Output is correct
10 Correct 180 ms 26744 KB Output is correct
11 Correct 181 ms 26904 KB Output is correct
12 Correct 185 ms 26788 KB Output is correct
13 Correct 170 ms 26740 KB Output is correct
14 Correct 174 ms 26892 KB Output is correct
15 Correct 170 ms 26768 KB Output is correct
16 Correct 163 ms 26836 KB Output is correct
17 Correct 168 ms 26836 KB Output is correct
18 Correct 176 ms 26728 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -