Submission #1257693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257693		Bahamin	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1467 ms	108844 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
#define lid id << 1
#define rid id << 1 | 1
#define mid ((r + l) >> 1)
const int MAX_N = 1e6 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

set<int> cnt[MAX_N];
int ma[MAX_N];
int n;
int seg[MAX_N << 2];
int ops[MAX_N << 2];

void build(int l, int r, int id)
{
    if (l == r - 1)
    {
        seg[id] = ma[l];
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

void move(int l, int r, int id)
{
    if (l == r - 1) return;
    seg[lid] += ops[id];
    seg[rid] += ops[id];
    ops[lid] += ops[id];
    ops[rid] += ops[id];
    ops[id] = 0;
}

void upd(int s, int t, int x, int l, int r, int id)
{
    if (s >= t) return;
    move(l, r, id);
    if (s <= l && t >= r) 
    {
        seg[id] += x;
        ops[id] += x;
        return;
    }
    if (s < mid) upd(s, t, x, l, mid, lid);
    if (t > mid) upd(s, t, x, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

void add(int x, int y, int l, int r, int id)
{
    move(l, r, id);
    if (l == r - 1)
    {
        seg[id] += (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
        cnt[l].insert(y);
        seg[id] -= (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
        return;
    }
    if (x < mid) add(x, y, l, mid, lid);
    else add(x, y, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

void rem(int x, int y, int l, int r, int id)
{
    move(l, r, id);
    if (l == r - 1)
    {
        seg[id] += (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
        cnt[l].erase(y);
        seg[id] -= (cnt[l].size() ? (n - *cnt[l].rbegin() - 1) : INF);
        return;
    }
    if (x < mid) rem(x, y, l, mid, lid);
    else rem(x, y, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

vector<int> countScans(vector<int> a, vector<int> xx, vector<int> vv)
{
	int q = xx.size();
    n = a.size();
    vector<int> answer(q);
    vector<int> al;
    for (int x : a) al.push_back(x);
    for (int x : vv) al.push_back(x);
    sort(all(al));
    al.resize(unique(all(al)) - al.begin()); 
    for (int i = 0; i < n; i++) a[i] = lower_bound(all(al), a[i]) - al.begin(), cnt[a[i]].insert(i);
    for (int i = 0; i < q; i++) vv[i] = lower_bound(all(al), vv[i]) - al.begin();
    int sum = 0;
    for (int i = al.size() - 1; i >= 0; i--)
    {
        ma[i] = sum - (cnt[i].size() ? (n - *cnt[i].rbegin() - 1) : INF);
        sum += cnt[i].size();
    }
    build(0, al.size(), 1);
	for (int i = 0; i < q; i++)
    {
        upd(0, a[xx[i]], -1, 0, al.size(), 1);
        rem(a[xx[i]], xx[i], 0, al.size(), 1);
        upd(0, vv[i], 1, 0, al.size(), 1);
        add(vv[i], xx[i], 0, al.size(), 1);
        a[xx[i]] = vv[i];
        answer[i] = seg[1];
    }
	return answer;
}

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