Submission #883986

#	Time	Username	Problem	Language	Result	Execution time	Memory
883986		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3709 ms	115460 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

using namespace std;
using ll = long long;

//#define int ll

#define sz(x) ((x).size())

using tii = tuple<int,int,int>;
using pii = pair<int,int>;

map<tii, int> nrm;

template<typename Node, typename Lazy>
struct AINT {
    vector<Node> aint;
    vector<Lazy> lazy;
    int n;
    void init(int _n) {
        n = _n;
        aint.resize(n * 2 + 5, Node());
        lazy.resize(n * 2 + 5, Lazy());
    }

    void upd(int p, Node x, int node, int cl, int cr) {
        if(p < cl || cr < p) return;
        if(cl == cr) { aint[node] = x; return; }
        int mid = cl + cr >> 1;
        push(node, (mid - cl + 1) * 2);
        upd(p, x, node + 1, cl, mid);
        upd(p, x, node + (mid - cl + 1) * 2, mid + 1, cr);
        aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
    }
    Node query(int l, int r, int node, int cl, int cr) {
        if(r < cl || cr < l) return Node();
        if(l <= cl && cr <= r) return aint[node];
        int mid = cl + cr >> 1;
        push(node, (mid - cl + 1) * 2);
        return query(l, r, node + 1, cl, mid) + query(l, r, node + (mid - cl + 1) * 2, mid + 1, cr);
    }

    void upd(int p, Node x) { upd(p, x, 1, 1, n); }
    Node query(int l, int r) { return query(l, r, 1, 1, n); }


    void push(int node, int L) {
        aint[node + 1] += lazy[node];
        aint[node + L] += lazy[node];
        lazy[node + 1] += lazy[node];
        lazy[node + L] += lazy[node];
        lazy[node] = Lazy();
    }
    void pushsegm(int l, int r, Lazy x, int node, int cl, int cr) {
        if(cr < l || r < cl) return;
        if(l <= cl && cr <= r) {
            aint[node] += x;
            lazy[node] += x;
            return;
        }

        int mid = cl + cr >> 1;
        push(node, (mid - cl + 1) * 2);

        pushsegm(l, r, x, node + 1, cl, mid);
        pushsegm(l, r, x, node + (mid - cl + 1) * 2, mid + 1, cr);
        aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
    }
    void pushsegm(int l, int r, Lazy x) { return pushsegm(l, r, x, 1, 1, n); }

};

namespace Trolling {
    int get(vector<int> V) {
        int n = sz(V);
        vector<int> idx(n);
        iota(all(idx), 0);
        sort(all(idx), [&](int a, int b) { return V[a] < V[b] || (V[a] == V[b] && a < b); } );
        int mx = 0, cnt = 0;
        for(auto x : idx)
    //        cerr << V[x] << ' ' << x << ' ' << cnt << '\n',
            mx = max(mx, x - cnt),
            cnt++;
        return mx;
    }
}

namespace DS {
    struct Lazy {
        int sum;
        Lazy(int a = 0): sum(a) {;}
        Lazy operator +(const Lazy &x) const { return Lazy(sum + x.sum); }
        Lazy operator +=(const Lazy &x) { return *this = Lazy(sum + x.sum); }
    };

    struct Node {
        int cnt, mx;
        Node(int a = 0, int b = 0): cnt(a), mx(b) {;}
        Node operator +(const Node& x) const { return Node(cnt + x.cnt, max(mx, x.mx)); }
        Node operator +(const Lazy& x) const { return Node(cnt, mx + x.sum); }
        Node operator +=(const Lazy& x) { return *this = Node(cnt, mx + x.sum); }
    };

    AINT<Node, Lazy> aint;

    int n;
    void init(int _n) {
        aint.init(n = _n);
    }

    void insert(int a, int b, int c) {
        int P = nrm[tii{a, b, c}];
        int counter = aint.query(1, P).cnt;
        aint.upd(P, Node(1, b - counter));
        aint.pushsegm(P + 1, n, Lazy(-1));

//        cerr << counter << ' ' << a << '\t' << b << '\t' << b - counter << '\n';

    }


    void erase(int a, int b, int c) {
        int P = nrm[tii{a, b, c}];
        aint.upd(P, Node(0, 0));
        aint.pushsegm(P + 1, n, Lazy(1));
    }

    int query() {
//        for(int i = 1; i <= n; i++)
//            cerr << aint.query(i, i).cnt << ' ' << aint.query(i, i).mx << '\n';
        return aint.query(1, n).mx;
    }

}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int Q=X.size(), n = sz(A);

	vector<int> lastupdate(n, -1);

	std::vector<int> answer(Q);
	for(int i = 0; i < n; i++) {
        nrm[tii{A[i], i, -1}];
	}
	for (int j=0;j<Q;j++) {
        nrm[tii{V[j], X[j], j}];
    }

    int cnt = 1;
    for(auto &[a, b] : nrm) b = cnt++;

    DS::init(cnt - 1);

    for(auto &[a, b] : nrm) {
        auto [L, R, W] = a;
        if(W == -1)
            DS::insert(L, R, W);
    }

    for(int j = 0; j < Q; j++) {
        DS::erase(A[X[j]], X[j], lastupdate[X[j]]);
        lastupdate[X[j]] = j;
        A[X[j]] = V[j];
        DS::insert(A[X[j]], X[j], lastupdate[X[j]]);

        answer[j] = DS::query();
    }

	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In instantiation of 'Node AINT<Node, Lazy>::query(int, int, int, int, int) [with Node = DS::Node; Lazy = DS::Lazy]':
bubblesort2.cpp:46:44:   required from 'Node AINT<Node, Lazy>::query(int, int) [with Node = DS::Node; Lazy = DS::Lazy]'
bubblesort2.cpp:115:38:   required from here
bubblesort2.cpp:40:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = cl + cr >> 1;
      |                   ~~~^~~~
bubblesort2.cpp: In instantiation of 'void AINT<Node, Lazy>::upd(int, Node, int, int, int) [with Node = DS::Node; Lazy = DS::Lazy]':
bubblesort2.cpp:45:34:   required from 'void AINT<Node, Lazy>::upd(int, Node) [with Node = DS::Node; Lazy = DS::Lazy]'
bubblesort2.cpp:116:41:   required from here
bubblesort2.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = cl + cr >> 1;
      |                   ~~~^~~~
bubblesort2.cpp: In instantiation of 'void AINT<Node, Lazy>::pushsegm(int, int, Lazy, int, int, int) [with Node = DS::Node; Lazy = DS::Lazy]':
bubblesort2.cpp:71:58:   required from 'void AINT<Node, Lazy>::pushsegm(int, int, Lazy) [with Node = DS::Node; Lazy = DS::Lazy]'
bubblesort2.cpp:117:41:   required from here
bubblesort2.cpp:64:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = cl + cr >> 1;
      |                   ~~~^~~~

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