oj.uz

Submission #884120

# Submission time Handle Problem Language Result Execution time Memory
884120 2023-12-06T16:00:40 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 246 ms 26996 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 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 8 ms 8952 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 8 ms 8952 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 20 ms 16220 KB Output is correct
2 Correct 115 ms 21668 KB Output is correct
3 Correct 227 ms 26840 KB Output is correct
4 Correct 203 ms 26832 KB Output is correct
5 Correct 217 ms 26836 KB Output is correct
6 Correct 218 ms 26836 KB Output is correct
7 Correct 246 ms 26848 KB Output is correct
8 Correct 246 ms 26844 KB Output is correct
9 Correct 234 ms 26996 KB Output is correct
10 Correct 206 ms 26896 KB Output is correct
11 Correct 176 ms 26836 KB Output is correct
12 Correct 184 ms 26836 KB Output is correct
13 Correct 173 ms 26832 KB Output is correct
14 Correct 172 ms 26836 KB Output is correct
15 Correct 192 ms 26844 KB Output is correct
16 Correct 190 ms 26816 KB Output is correct
17 Correct 174 ms 26796 KB Output is correct
18 Correct 185 ms 26836 KB Output is correct

Subtask #4
0 / 40.0

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