Submission #380623

#	Time	Username	Problem	Language	Result	Execution time	Memory
380623		ntabc05101	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3651 ms	128992 KiB

bubblesort2

#if not LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

const int inf=1e9+9;

struct SegmentTree {
        std::vector<int64_t> nodes, lazy;
        std::vector<int> L, H;

        void buildRange(int node, int low, int high) {
                L[node]=low, H[node]=high;
                nodes[node]=lazy[node]=0;
                if (low==high) {
                        return ;
                }

                int mid=(low+high)>>1;
                buildRange(node<<1, low, mid);
                buildRange(node<<1|1, mid+1, high);
        }

        SegmentTree(int n) {
                nodes.resize(n<<2); lazy.resize(n<<2);
                L.resize(n<<2), H.resize(n<<2);
                buildRange(1, 1, n);
        }

        void propagate(int node) {
                auto& t=lazy[node];

                nodes[node<<1]+=t;
                lazy[node<<1]+=t;
                nodes[node<<1|1]+=t;
                lazy[node<<1|1]+=t;

                t=0;
        }


        void update(int node, int leftq, int rightq, int delta) {
                //std::cout<<node<<" "<<L[node]<<" "<<H[node]<<" "<<leftq<<" "<<rightq<<" "<<delta<<"\n";
                if (leftq<=L[node] and rightq>=H[node]) {
                        nodes[node]+=delta;
                        lazy[node]+=delta;
                        return ;
                }

                propagate(node);
                if (H[node<<1]>=leftq) update(node<<1, leftq, rightq, delta);
                if (L[node<<1|1]<=rightq) update(node<<1|1, leftq, rightq, delta);

                nodes[node]=std::max(nodes[node<<1], nodes[node<<1|1]);
        }
};

std::vector<int> countScans(std::vector<int> a, std::vector<int> x, std::vector<int> v) {
        int n=a.size(), q=v.size();

        std::vector< std::pair<int, int> > num;
        for (int i=0; i<n; i++) {
                num.push_back({a[i], i});
        }
        for (int i=0; i<q; i++) {
                num.push_back({v[i], x[i]});
        }

        std::sort(begin(num), end(num));
        num.erase(std::unique(begin(num), end(num)), end(num));

        int s=num.size();

        //std::cout<<s<<"\n";

        SegmentTree seg(s);
        seg.update(1, 1, s, -inf);

        const auto ins=[&](int p, int r) {
                int i=std::lower_bound(begin(num), end(num), std::make_pair(p, r))-begin(num)+1;
                seg.update(1, i, i, inf+r);
                if (i<s) {
                        seg.update(1, i+1, s, -1);
                }
        };
        const auto ers=[&](int p, int r) {
                int i=std::lower_bound(begin(num), end(num), std::make_pair(p, r))-begin(num)+1;
                seg.update(1, i, i, -inf-r);
                if (i<s) {
                        seg.update(1, i+1, s, 1);
                }
        };

        for (int i=0; i<n; i++) {
                ins(a[i], i);
        }

        std::vector<int> result(q);
        for (int i=0; i<q; i++) {
                ers(a[x[i]], x[i]);
                ins(v[i], x[i]);
                a[x[i]]=v[i];
                result[i]=seg.nodes[1];
        }

        return result;
}

/*int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n, q; std::cin>>n>>q;
        std::vector<int> a(n), x(q), v(q);
        for (auto& _: a) std::cin>>_;
        for (int i=0; i<q; i++) std::cin>>x[i]>>v[i];

        auto result=countScans(a, x, v);
        for (int i=0; i<q; i++) std::cout<<result[i]<<" ";

        std::cout<<std::endl;

        return 0;
}*/

/*
4 2
1 2 3 4
0 3
2 1
*/

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