oj.uz

Submission #884098

# Submission time Handle Problem Language Result Execution time Memory
884098 2023-12-06T15:53:07 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 259 ms 27144 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;
        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 i = 0;i < n;i++){
                ans2 = max(ans2,fen.get(v[i]));
                fen.add(v[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
**/

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16220 KB Output is correct
2 Correct 137 ms 21764 KB Output is correct
3 Correct 213 ms 26888 KB Output is correct
4 Correct 241 ms 26832 KB Output is correct
5 Correct 234 ms 26748 KB Output is correct
6 Correct 225 ms 26892 KB Output is correct
7 Correct 239 ms 26832 KB Output is correct
8 Correct 259 ms 26964 KB Output is correct
9 Correct 231 ms 26916 KB Output is correct
10 Correct 224 ms 26832 KB Output is correct
11 Correct 195 ms 26840 KB Output is correct
12 Correct 195 ms 26888 KB Output is correct
13 Correct 189 ms 26800 KB Output is correct
14 Correct 193 ms 26828 KB Output is correct
15 Correct 189 ms 26904 KB Output is correct
16 Correct 188 ms 27144 KB Output is correct
17 Correct 188 ms 26832 KB Output is correct
18 Correct 181 ms 26824 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -