oj.uz

답안 #690945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
690945 2023-01-30T18:03:18 Z Ahmed57 Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 11 ms 1296 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;
int seg[2][2000001];
int 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<int> 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;
        int 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

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:20: 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: 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 | }
      | ^

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -