oj.uz

Submission #225449

# Submission time Handle Problem Language Result Execution time Memory
225449 2020-04-20T15:08:34 Z MKopchev Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 30 ms 1532 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

const int nmax=2*5e5+42;

struct info
{
    int maxi,lazy;
};

info tree[4*nmax];

void push(int node)
{
    tree[node*2].lazy+=tree[node].lazy;
    tree[node*2+1].lazy+=tree[node].lazy;
    tree[node].lazy=0;
}

info actual(info ret)
{
    ret.maxi+=ret.lazy;
    ret.lazy=0;
    return ret;
}

info my_merge(info a,info b)
{
    a=actual(a);
    b=actual(b);

    if(a.maxi<b.maxi)return b;
    return a;
}
void update_single(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node].maxi=val;
        return;
    }

    push(node);

    int av=(l+r)/2;

    if(pos<=av)update_single(node*2,l,av,pos,val);
    else update_single(node*2+1,av+1,r,pos,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void update_range(int node,int l,int r,int lq,int rq,int val)
{
    if(l==lq&&r==rq)
    {
        tree[node].lazy+=val;
        return;
    }
    push(node);

    int av=(l+r)/2;

    if(lq<=av)update_range(node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update_range(node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V)
{
    vector< pair<int,int> > active={};
    for(int i=0;i<A.size();i++)
        active.push_back({A[i],i});

    for(int i=0;i<X.size();i++)
        active.push_back({V[i],X[i]});

    sort(active.begin(),active.end());

    unique(active.begin(),active.end());

    int n=active.size()-1;

    for(int i=0;i<A.size();i++)
    {
        int pos=lower_bound(active.begin(),active.end(),make_pair(A[i],i))-active.begin();

        update_single(1,0,n,pos,i);

        if(pos+1<=n)update_range(1,0,n,pos+1,n,-1);
    }

    vector<int> output={};

    for(int i=0;i<X.size();i++)
    {
        int pos=lower_bound(active.begin(),active.end(),make_pair(A[i],i))-active.begin();

        update_single(1,0,n,pos,-1e9);

        if(pos+1<=n)update_range(1,0,n,pos+1,n,1);

        A[X[i]]=V[i];

        pos=lower_bound(active.begin(),active.end(),make_pair(V[i],X[i]))-active.begin();

        update_single(1,0,n,pos,X[i]);

        if(pos+1<=n)update_range(1,0,n,pos+1,n,-1);

        output.push_back(actual(tree[1]).maxi);
    }
    return output;
}
/*
int main()
{
    vector<int> A={1,2,3,4};
    vector<int> X={0,2};
    vector<int> V={3,1};

    for(auto k:countScans(A,X,V))cout<<k<<endl;

    return 0;
}
*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
bubblesort2.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++)
                 ~^~~~~~~~~
bubblesort2.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
bubblesort2.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++)
                 ~^~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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