Submission #469520

#	Time	Username	Problem	Language	Result	Execution time	Memory
469520		Lam_lai_cuoc_doi	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	682 ms	493968 KiB

bubblesort2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr int Inf = 1e9 + 7;

struct FenwickTree
{
    int a[N];
    int n;
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    int Get(int p)
    {
        int ans(0);
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }
} g;

struct SegmentTree
{
    int n;
    int lazy[N * 8], st[N * 8];

    SegmentTree()
    {
        memset(lazy, 0, sizeof lazy);
        fill_n(st, N * 8, -Inf);
    }
    void Push(int id)
    {
        if (lazy[id] != 0)
        {
            if (st[id << 1] != -Inf)
                st[id << 1] += lazy[id];
            lazy[id << 1] += lazy[id];
            if (st[id << 1 | 1] != -Inf)
                st[id << 1 | 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
            lazy[id] = 0;
        }
    }
    void Update(int id, int l, int r, const int &x, const int &v)
    {
        if (l > x || r < x)
            return;
        if (l == x && r == x)
        {
            st[id] = v;
            return;
        }
        Push(id);
        Update(id << 1, l, (l + r) / 2, x, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int x, int v)
    {
        Update(1, 1, n, x, v);
    }
    void Update(int id, int l, int r, const int &a, const int &b, const int &v)
    {
        if (l > b || r < a)
            return;
        if (l >= a && r <= b)
        {
            st[id] += v;
            lazy[id] += v;
            return;
        }
        Push(id);
        Update(id << 1, l, (l + r) / 2, a, b, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int l, int r, int v)
    {
        Update(1, 1, n, l, r, v);
    }
} f;

vector<int> s;
set<int> pos[N * 8];
int n, m;

#define Find(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin() + 1)

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
    vector<int> ans(x.size(), 0);

    n = a.size();
    m = x.size();

    for (int i = 0; i < n; ++i)
        s.emplace_back(a[i]);
    for (int i = 0; i < m; ++i)
        s.emplace_back(v[i]);

    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
    f.n = g.n = s.size();

    for (int i = 0; i < n; ++i)
    {
        a[i] = Find(s, a[i]);
        g.Update(a[i], 1);
        pos[a[i]].insert(i);
    }

    for (int i = 0; i < (int)s.size(); ++i)
        if (!pos[i + 1].empty())
            f.Update(i + 1, *pos[i + 1].rbegin() + 1 - g.Get(i + 1));

    for (int i = 0; i < m; ++i)
    {
        v[i] = Find(s, v[i]);

        pos[a[x[i]]].erase(x[i]);
        f.Update(a[x[i]], s.size(), 1);
        g.Update(a[x[i]], -1);

        if (pos[a[x[i]]].empty())
            f.Update(a[x[i]], -Inf);
        else
            f.Update(a[x[i]], *pos[a[x[i]]].rbegin() + 1 - g.Get(a[x[i]]));

        a[x[i]] = v[i];

        pos[a[x[i]]].insert(x[i]);
        f.Update(a[x[i]], s.size(), -1);
        g.Update(a[x[i]], 1);
        f.Update(v[i], *pos[v[i]].rbegin() + 1 - g.Get(v[i]));

        ans[i] = f.st[1];
    }

    return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void read(T&)':
bubblesort2.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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