Submission #124327

#	Time	Username	Problem	Language	Result	Execution time	Memory
124327		arnold518	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2600 ms	119464 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const int MAXQ = 5e5;
const ll NEGINF = -1e17;

int N, Q, S;
vector<ll> A, X, V, comp;
vector<int> ans;

ll getcomp(ll x)
{
    return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
}

struct SEG
{
    int N;
    vector<ll> tree, lazy;
    SEG(int N) : N(N), tree(4*N+10, NEGINF), lazy(4*N+10, 0ll) {}

    void busy(int node, int tl, int tr)
    {
        if(lazy[node]==0) return;
        tree[node]+=lazy[node];
        if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node];
        lazy[node]=0;
    }

    void update_range(int node, int tl, int tr, int l, int r, ll val)
    {
        busy(node, tl, tr);
        if(tr<l || r<tl) return;
        if(l<=tl && tr<=r)
        {
            tree[node]+=val;
            if(tl!=tr) lazy[node*2]+=val, lazy[node*2+1]+=val;
            return;
        }
        int mid=tl+tr>>1;
        update_range(node*2, tl, mid, l, r, val);
        update_range(node*2+1, mid+1, tr, l, r, val);
        tree[node]=max(tree[node*2], tree[node*2+1]);
        //printf("!!!!!%d %d %d %d %d %lld : %lld %lld\n", node, tl, tr, l, r, val, tree[node], lazy[node]);
    }

    void update_change(int node, int tl, int tr, int pos, ll val)
    {
        busy(node, tl, tr);
        if(tl==tr)
        {
            tree[node]+=val;
            return;
        }
        int mid=tl+tr>>1;
        if(pos<=mid) update_change(node*2, tl, mid, pos, val);
        else update_change(node*2+1, mid+1, tr, pos, val);
        tree[node]=max(tree[node*2]+lazy[node*2], tree[node*2+1]+lazy[node*2+1]);
    }

    ll read(int node, int tl, int tr, int pos)
    {
        busy(node, tl, tr);
        if(tl==tr) return tree[node];
        int mid=tl+tr>>1;
        if(pos<=mid) return read(node*2, tl, mid, pos);
        else return read(node*2+1, mid+1, tr, pos);
    }

    void update_change(int pos, ll val)
    {
        //printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!%lld\n", read(1, 1, N, pos));
        update_change(1, 1, N, pos, val-read(1, 1, N, pos));
    }

    void debug(int node, int tl, int tr)
    {
        busy(node, tl, tr);
        if(tl==tr)
        {
            //printf("(%d : %lld) ", tl, tree[node]);
            return;
        }
        int mid=tl+tr>>1;
        debug(node*2, tl, mid);
        debug(node*2+1, mid+1, tr);
    }

    ll query()
    {
        busy(1, 1, N);
        return tree[1];
    }
};

struct BIT
{
    int N;
    vector<ll> tree;
    BIT(int N) : N(N), tree(N+10, 0ll) {}
    void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]+=val; }
    ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
};

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
    int i, j;
    N=a.size(); Q=x.size();
    for(i=0; i<a.size(); i++) A.push_back((ll)a[i]*N+i), comp.push_back((ll)a[i]*N+i);
    for(i=0; i<x.size(); i++) V.push_back((ll)v[i]*N+x[i]), comp.push_back((ll)v[i]*N+x[i]);
    for(i=0; i<v.size(); i++) X.push_back((ll)x[i]);

    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    S=comp.size();

    for(i=0; i<N; i++) A[i]=getcomp(A[i]);
    for(i=0; i<Q; i++) V[i]=getcomp(V[i]);

    SEG seg(S);
    BIT bit(S);

    for(i=0; i<N; i++) bit.update(A[i], 1);
    for(i=0; i<N; i++) seg.update_change(A[i], i-bit.query(A[i]-1));

    //for(i=0; i<N; i++) printf("%lld ", A[i]); printf("\n");
    //seg.debug(1, 1, S); printf("\n");

    for(i=0; i<Q; i++)
    {
        ll pos=X[i], bef=A[pos], aft=V[i];
        bit.update(bef, -1);
        bit.update(aft, 1);

        if(bef<aft)
        {
            if(bef+1<=aft-1) seg.update_range(1, 1, S, bef+1, aft-1, 1);
            seg.update_change(bef, NEGINF);
            seg.update_change(aft, pos-bit.query(aft-1));
        }
        else
        {
            if(aft+1<=bef-1) seg.update_range(1, 1, S, aft+1, bef-1, -1);
            seg.update_change(bef, NEGINF);
            seg.update_change(aft, pos-bit.query(aft-1));
        }

        ans.push_back(seg.query());

        A[pos]=V[i];

        //printf("%lld %lld %lld\n", pos, bef, aft);
        //for(j=0; j<N; j++) printf("%lld ", A[j]); printf("\n");
        //seg.debug(1, 1, S); //printf("\n");
    }
    return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In member function 'void SEG::update_range(int, int, int, int, int, ll)':
bubblesort2.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In member function 'void SEG::update_change(int, int, int, int, ll)':
bubblesort2.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In member function 'll SEG::read(int, int, int, int)':
bubblesort2.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In member function 'void SEG::debug(int, int, int)':
bubblesort2.cpp:90:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:115:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<a.size(); i++) A.push_back((ll)a[i]*N+i), comp.push_back((ll)a[i]*N+i);
              ~^~~~~~~~~
bubblesort2.cpp:116:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<x.size(); i++) V.push_back((ll)v[i]*N+x[i]), comp.push_back((ll)v[i]*N+x[i]);
              ~^~~~~~~~~
bubblesort2.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); i++) X.push_back((ll)x[i]);
              ~^~~~~~~~~
bubblesort2.cpp:113:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40