Submission #210816

#	Time	Username	Problem	Language	Result	Execution time	Memory
210816		eric_xiao	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	84 ms	2776 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
#define ll long long
#define MOD 10000000007
using namespace std;
int N,Q,sz;
int ST[6000009],tag[6000009];
void push(int p,int l,int r)
{
    if(r == l+1) return;
    tag[p*2] += tag[p];
    tag[p*2+1] += tag[p];
    ST[p*2] += tag[p];
    ST[p*2+1] += tag[p];
    tag[p] = 0;
    return;
}
void Build(int p,int l,int r)
{
    ST[p] = 0;
    if(r == l + 1) return;
    int mid = (l + r)/2;
    Build(p*2,l,mid);
    Build(p*2+1,mid,r);
}
void Modify(int p,int l,int r,int ql,int qr,int k)
{
    if(l >= ql && r <= qr)
    {
        tag[p] += k;
        ST[p] += k;
        return;
    }
    if(l >= qr || r <= ql) return;
    push(p,l,r);
    int mid = (l + r)/2;
    Modify(p*2,l,mid,ql,qr,k);
    Modify(p*2+1,mid,r,ql,qr,k);
    ST[p] = max(ST[p*2+1],ST[p*2]);
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V)
{
    int i;
    vector<int> ans;
    N = A.size();
    Q = X.size();
    vector<ll> v;
    for(i = 0;i < N;i++) v.push_back((ll)A[i]*(ll)MOD + (ll)i);
    for(i = 0;i < Q;i++) v.push_back((ll)V[i]*(ll)MOD + (ll)i);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    sz = v.size() + 20;
    for(i = 0;i < N;i++)
    {
        A[i] = lower_bound(v.begin(),v.end(),(ll)A[i]*(ll)MOD + (ll)i) - v.begin() + 1;
    }
    for(i = 0;i < Q;i++)
    {
        V[i] = lower_bound(v.begin(),v.end(),(ll)V[i]*(ll)MOD + (ll)i) - v.begin() + 1;
    }
    Build(1,0,sz);
    for(i = 0;i < N;i++)
    {
        Modify(1,0,sz,A[i],A[i]+1,i);
    }
    for(i = 0;i < N;i++)
    {
        Modify(1,0,sz,A[i]+1,sz,-1);
    }
    for(i = 0;i < Q;i++)
    {
        int x = X[i],v = V[i];
        Modify(1,0,sz,A[x]+1,sz,1);
        Modify(1,0,sz,v+1,sz,-1);
        Modify(1,0,sz,A[x],A[x]+1,-x);
        Modify(1,0,sz,v,v+1,x);
        A[x] = v;
        //cout << ST[1] << endl;
        ans.push_back(ST[1]);
        assert(ST[1] >= 0);
    }
    return ans;
}

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