Submission #1013256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013256		cpdreamer	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	491 ms	59472 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define pb push_back
#define P pair
#define F first
#define S second

struct segtree{
private:
    struct node{
        vector<int>count;
    };
    static node make_neutral(){
        vector<int>A;
        A.assign(101,0);
        return{A};
    }
    static node single(int v){
        vector<int>A;
        A.assign(101,0);
        A[v]++;
        return{A};
    }
    static node merge(node &a,node &b){
        node c{};
        c.count.assign(101,0);
        for(int i=0;i<101;i++){
            c.count[i]=a.count[i]+b.count[i];
        }
        return c;
    }
public:
    int size;
    vector<node>query;
    void init(int n){
        size=1;
        while(size<n)size*=2;
        query.assign(2*size,make_neutral());
    }
    void set(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            query[x]=single(v);
            return;
        }
        int m=(lx+rx)/2;
        if(i<m)
            set(i,v,2*x+1,lx,m);
        else
            set(i,v,2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void set(int i,int v){
        set(i,v,0,0,size);
    }
    node calc(int l,int r,int x,int lx,int rx){
        if(lx>=r || rx<=l)
            return make_neutral();
        if(l<=lx && rx<=r)
            return query[x];
        int m=(lx+rx)/2;
        node a=calc(l,r,2*x+1,lx,m);
        node b=calc(l,r,2*x+2,m,rx);
        return merge(a,b);
    }
    vector<int>  calc(int l,int r){
        return calc(l,r,0,0,size).count;
    }
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    int Q=X.size();
    std::vector<int> answer;
    int n=A.size();
    stack<P<int,int>> best[101];
    segtree tree;
    tree.init(n);
    for(int i=0;i<n;i++)
        tree.set(i,A[i]);
    for(int i=0;i<n;i++){
        vector<int>c=tree.calc(0,i+1);
        int calc=0;
        for(int j=A[i]+1;j<=100;j++){
            calc+=c[j];
        }
        best[A[i]].push({i,calc});
    }
    for(int i=0;i<Q;i++){
        int prev=A[X[i]];
        int nex=V[i];
        int ind=X[i];
        tree.set(ind,nex);
        A[ind]=nex;
        if(ind==best[prev].top().F){
            best[prev].pop();
            if(!best[prev].empty()){
                vector<int>c=tree.calc(0,best[prev].top().F+1);
                int calc=0;
                for(int j=prev+1;j<=100;j++){
                    calc+=c[j];
                }
                best[prev].top().S=calc;
            }
        }
        if(best[nex].empty()){
            vector<int>c=tree.calc(0,ind+1);
            int calc=0;
            for(int j=nex+1;j<=100;j++){
                calc+=c[j];
            }
            best[nex].push({ind,calc});
        }
        else {
            if (ind > best[nex].top().F) {
                vector<int> c = tree.calc(0, ind+1);
                int calc = 0;
                for (int j = nex + 1; j <= 100; j++) {
                    calc += c[j];
                }
                best[nex].push({ind, calc});
            }
        }
        for(int j=1;j<=100;j++){
            if(!best[j].empty()) {
                if (best[j].top().F > ind) {
                    if (nex > A[best[j].top().F] && A[best[j].top().F] >= prev) {
                        best[j].top().S++;
                    }
                    if (nex <= A[best[j].top().F] && A[best[j].top().F] < prev) {
                        best[j].top().S--;
                    }
                }
            }
        }
        int max_d=0;
        for(int j=1;j<=100;j++){
            if(!best[j].empty()) {
                max_d = max(max_d, best[j].top().S);
            }
        }
        answer.pb(max_d);
    }
    return answer;
}

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