oj.uz

Submission #851755

# Submission time Handle Problem Language Result Execution time Memory
851755 2023-09-20T14:26:43 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 6291 ms 68768 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int pr=23, s_p=1<<pr, e_p=(1<<(pr+1))-1;
int n;
vector<int>S_sum;

void pre(){
    S_sum.clear();
    S_sum.resize(1<<(pr+1));
}

void update(int ind, int c){
    S_sum[ind]+=c;
    while(ind/=2)
        S_sum[ind]+=c;
}

int get(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return 0;
    if(l>=u && r<=v)
        return S_sum[id];
    int md=(l+r)/2;
    return get(id*2, u, v, l, md)+get(id*2+1, u, v, md+1, r);
}

vector<int> countScans(vector<int>A, vector<int>X, vector<int>V){
    vector<int>S, All, Cur(A.size());
    n=A.size();
    int q=X.size();
    for(int i=0;i<n;i++){
        All.push_back(A[i]);
    }
    for(int i=0;i<q;i++){
        All.push_back(V[i]);
    }
    sort(all(All));
    int cur=1;
    map<int, int>mp;
    for(int i=0;i<All.size();i++){
        if(i==All.size()-1 || All[i]!=All[i+1])
            mp[All[i]]=cur++;
    }
    for(int i=0;i<n;i++){
        A[i]=mp[A[i]];
    }
    pre();
    for(int i=0;i<n;i++){
        int cur=get(1, s_p+A[i]+1, e_p, s_p, e_p);
        Cur[i]=cur;
        update(s_p+A[i], 1);
    }
    for(int i=0;i<n;i++){
        update(s_p+A[i], -1);
    }
    for(int k=0;k<q;k++){
        int ind=X[k], val=V[k];
        bool larger=(val>A[ind]);
        int mx=0, inc=0;
        for(int i=0;i<ind;i++){
            if(!larger){
                inc+=(A[i]<=A[ind] && A[i]>val);
            }
            else{
                inc-=(A[i]>A[ind] && A[i]<=val);
            }
        }
        Cur[ind]+=inc;
        for(int i=ind+1;i<n;i++){
            if(!larger){
                Cur[i]-=(A[i]<A[ind] && A[i]>=val);
            }
            else{
                Cur[i]+=(A[i]<val && A[i]>=A[ind]);
            }
        }
        A[ind]=val;
        for(int i=0;i<n;i++){
            mx=max(mx, Cur[i]);
        }
        S.push_back(mx);
    }
    return S;
}

//int main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);
//    int n, q;
//    cin>>n>>q;
//    vector<int>A(n), X(q), V(q);
//    for(int i=0;i<n;i++){
//        cin>>A[i];
//    }
//    for(int j=0;j<q;j++){
//        cin>>X[j]>>V[j];
//    }
//    vector<int>Ans=countScans(A, X, V);
//    for(int i=0;i<q;i++){
//        cout<<Ans[i]<<endl;
//    }
//}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<All.size();i++){
      |                 ~^~~~~~~~~~~
bubblesort2.cpp:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(i==All.size()-1 || All[i]!=All[i+1])
      |            ~^~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 66136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 66136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 66684 KB Output is correct
2 Correct 2461 ms 67572 KB Output is correct
3 Correct 6291 ms 68244 KB Output is correct
4 Correct 6269 ms 68272 KB Output is correct
5 Correct 6066 ms 68292 KB Output is correct
6 Correct 6009 ms 68560 KB Output is correct
7 Correct 5815 ms 68348 KB Output is correct
8 Correct 5876 ms 68344 KB Output is correct
9 Correct 5880 ms 68512 KB Output is correct
10 Correct 4930 ms 68536 KB Output is correct
11 Correct 4948 ms 68516 KB Output is correct
12 Correct 4954 ms 68112 KB Output is correct
13 Correct 4862 ms 68308 KB Output is correct
14 Correct 4878 ms 68768 KB Output is correct
15 Correct 4873 ms 68576 KB Output is correct
16 Correct 4808 ms 68508 KB Output is correct
17 Correct 4818 ms 68444 KB Output is correct
18 Correct 4811 ms 68516 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 66136 KB Output isn't correct
2 Halted 0 ms 0 KB -