Submission #690946

#	Time	Username	Problem	Language	Result	Execution time	Memory
690946		Ahmed57	Bubble Sort 2 (JOI18_bubblesort2)	C++14	Compilation error	0 ms	0 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;
long long seg[2][2000001];
long long arr[500001];
void build(int p,int l,int r){
    if(l==r){
        seg[0][p] = arr[l];
        seg[1][p] = arr[l];
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[0][p] = min(seg[0][p*2],seg[0][p*2+1]);
    seg[1][p] = max(seg[1][p*2],seg[1][p*2+1]);
}
void update(int p,int l,int r,int ind){
    if(l==r){
        seg[0][p] = arr[l];
        seg[1][p] = arr[l];
        return ;
    }
    int md = (l+r)/2;
    if(ind<=md)update(p*2,l,md,ind);
    else update(p*2+1,md+1,r,ind);
    seg[0][p] = min(seg[0][p*2],seg[0][p*2+1]);
    seg[1][p] = max(seg[1][p*2],seg[1][p*2+1]);
}
long long qu(int p,int l,int r,int lq,int rq,int ty){
    if(l>=lq&&r<=rq)return seg[ty][p];
    if(r<lq||l>rq)return (ty==0?1e18:-1e18);
    int md = (l+r)/2;
    if(ty==0)return min(qu(p*2,l,md,lq,rq,ty),qu(p*2+1,md+1,r,lq,rq,ty));
    if(ty==1)return max(qu(p*2,l,md,lq,rq,ty),qu(p*2+1,md+1,r,lq,rq,ty));
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
    for(int i=  0;i<A.size();i++)arr[i+1] = A[i];
    build(1,1,A.size());
    vector<long long> d;
    for(int i= 0;i<X.size();i++){
        arr[X[i]+1]= V[i];
        update(1,1,A.size(),X[i]+1);
        long long ans = 0;
        long long l = 1 , r = X[i];
        while(l<=r){
            long long mid = (l+r)/2;
            if(qu(1,1,A.size(),1,mid,1)>V[i]){
                ans=max(ans,(X[i]+1)-mid);
                r = mid-1;
            }else l = mid+1;
        }
        l = X[i]+2,r = A.size();
        while(l<=r){
            long long mid = (l+r)/2;
            if(qu(1,1,A.size(),mid,A.size(),0)<V[i]){
                ans=max(ans,mid-(X[i]+1));
                l=mid+1;
            }else r = mid-1;
        }
        d.push_back(ans);
    }
    return d;
}
/*int main(){
    vector<int> v= countScans({1,2,3,4},{0,2},{3,1});
    for(auto i:v)cout<<i<<"\n";
}*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=  0;i<A.size();i++)arr[i+1] = A[i];
      |                   ~^~~~~~~~~
bubblesort2.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i= 0;i<X.size();i++){
      |                  ~^~~~~~~~~
bubblesort2.cpp:64:12: error: could not convert 'd' from 'vector<long long int>' to 'vector<int>'
   64 |     return d;
      |            ^
      |            |
      |            vector<long long int>
bubblesort2.cpp: In function 'long long int qu(int, int, int, int, int, int)':
bubblesort2.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
   37 | }
      | ^