Submission #124312

#	Time	Username	Problem	Language	Result	Execution time	Memory
124312		arnold518	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	30 ms	3316 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]);
    }

    ll query(int node, int tl, int tr, int l, int r)
    {
        busy(node, tl, tr);
        if(tr<l || r<tl) return NEGINF;
        if(l<=tl && tr<=r) return tree[node];
        int mid=tl+tr>>1;
        return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
    }

    void update_change(int pos, ll val)
    {
        update_range(1, 1, N, pos, pos, val-query(1, 1, N, pos, pos));
    }
};

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<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(1, 1, S, 1, S));

        A[pos]=V[i];
    }
    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 'll SEG::query(int, int, int, int, int)':
bubblesort2.cpp:57: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:80: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:81: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:82: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:78:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

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