oj.uz

Submission #765784

# Submission time Handle Problem Language Result Execution time Memory
765784 2023-06-25T05:12:39 Z normankr07 Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 1657 ms 67884 KB 
/*
Templete by norman/KNN-07
Who tf even love CP :sob:
*/
#ifndef LOCAL
#include "bubblesort2.h"
#endif
#include <bits/stdc++.h>

// Wish you can debug? YesYes
#ifndef LOCAL
#define cerr \
    if (0)   \
    cerr
#endif

// Policy based DS?
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

#pragma GCC optimize("Ofast,unroll-loops,inline")
// Bitwise pragma fuck
// #pragma GCC target("avx,avx2,bmi")

// Who tf deal with overflow
// #define int long long

/*
pbds blog :
https://codeforces.com/blog/entry/11080
https://codeforces.com/blog/entry/13279
*/
// Useful pbds
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
// typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("arch=skylake")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
using namespace std;

#define el '\n'
#define mpp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define emp emplace_back
#define fi first
#define nd second
#define forinc(i, a, b) for (int i = (a); i <= (b); i++)
#define fordec(i, a, b) for (int i = (a); i >= (b); i--)
#define alle(x) (x).begin(), (x).end()
#define ralle(x) (x).rbegin(), (x).rend()
#define mms(a, v) memset(a, v, sizeof(a))
#define lwb(a, v) lower_bound((a).begin(), (a).end(), v)
#define upb(a, v) upper_bound((a).begin(), (a).end(), v)
#define bit(i, a) (((a) >> (i)) & 1)

#define BIT_SET(a, b) ((a) |= (1ULL << (b)))
#define BIT_CLEAR(a, b) ((a) &= ~(1ULL << (b)))
#define BIT_FLIP(a, b) ((a) ^= (1ULL << (b)))
#define BIT_CHECK(a, b) (!!((a) & (1ULL << (b))))
#define BITMASK_SET(x, mask) ((x) |= (mask))
#define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
#define BITMASK_FLIP(x, mask) ((x) ^= (mask))
#define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
#define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
#define POPCNT(mask) __builtin_popcount(mask)
#define POPCNTLL(mask) __builtin_popcountll(mask)
#define CTZ(mask) __builtin_ctz(mask)
#define CTZLL(mask) __builtin_ctzll(mask)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef vector<bool> vb;

template <typename T, typename U>
inline void maximize(T &x, U y)
{
    if (y < x)
        x = y;
}
template <typename T, typename U>
inline void minimize(T &x, U y)
{
    if (x < y)
        x = y;
}
inline int add_m(int a, int b, int mod)
{
    int res = a + b;
    return (res >= mod ? res - mod : res);
}
inline int mod_neg(int a, int b, int mod)
{
    int res;
    if (abs(a - b) < mod)
        res = a - b;
    else
        res = (a - b) % mod;
    return (res < 0 ? res + mod : res);
}
inline int mul_wmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return (res >= c ? res % c : res);
}
inline int mul_wnmod(int a, int b, int c)
{
    ll res = (ll)a * b;
    return ((res % c) + c) % c;
}

// Debugger Utils
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

template <size_t i, class T>
ostream &print_tuple_utils(ostream &out, const T &tup)
{
    if constexpr (i == tuple_size<T>::value)
        return out << ")";
    else
        return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
}
template <class... U>
ostream &operator<<(ostream &out, const tuple<U...> &t)
{
    return print_tuple_utils<0, tuple<U...>>(out, t);
}
#define db(val) "[" #val " = " << (val) << "] "
// End if debugger utils

namespace Hasher
{
    struct custom_hash
    {
        static uint32_t splitmix64(uint32_t x)
        {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }
        size_t operator()(uint64_t x) const
        {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    struct hash_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = custom_hash{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
    struct hash_pair_pair
    {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2> &p) const
        {
            auto hash1 = custom_hash{}(p.first);
            auto hash2 = hash_pair{}(p.second);
            if (hash1 != hash2)
                return hash1 ^ hash2;
            return hash1;
        }
    };
}
using namespace Hasher;

const string taskname = "";
const bool tc = false;

const int oo = 1e9, mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll ool = 1e18;
const ldb eps = 1e-6;
const int MAXN = 1e6;

/*
Author: normankr07
Problem:

Submission links:

Editorial links:

Algorithm:
*/

struct MaxST
{
    struct STNode
    {
        ll lazy;
        ll val;
    };
    int n, a[MAXN];
    STNode t[4 * MAXN];
    void downtree(int v)
    {
        auto &cur = t[v];
        t[v * 2].lazy += cur.lazy;
        t[v * 2].val += cur.lazy;
        t[v * 2 + 1].lazy += cur.lazy;
        t[v * 2 + 1].val += cur.lazy;
        cur.lazy = 0;
    }
    void update(int v, int tl, int tr, int l, int r, int addend)
    {
        if (l > r)
            return;
        if (l == tl && tr == r)
        {
            t[v].val += addend;
            t[v].lazy += addend;
        }
        else
        {
            downtree(v);
            int tm = (tl + tr) / 2;
            update(v * 2, tl, tm, l, min(r, tm), addend);
            update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
            t[v].val = max(t[v * 2].val, t[v * 2 + 1].val);
        }
    }

    int query(int v, int tl, int tr, int l, int r)
    {
        if (l > r)
            return INT_MIN;
        if (l == tl && tr == r)
            return t[v].val;
        downtree(v);
        int tm = (tl + tr) / 2;
        return max(query(v * 2, tl, tm, l, min(r, tm)),
                   query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    }
} f;

vi countScans(vi a, vi x, vi v)
{
    int n = a.size();
    int q = x.size();
    // pair (val ,id);
    vi ans(q);
    vector<pii> compress;
    for (int i = 0; i < n; i++)
    {
        compress.pb({a[i], i});
    }
    for (int i = 0; i < q; i++)
    {
        compress.pb({v[i], x[i]});
    }
    sort(alle(compress));
    compress.erase(unique(alle(compress)), compress.end());
    int sz = compress.size();
    for (int i = 0; i < n; i++)
    {
        int pos = lwb(compress, mpp(a[i], i)) - compress.begin() + 1;
        f.update(1, 1, sz, pos, pos, i + 1);
        f.update(1, 1, sz, pos, sz, -1);
    }
    for (int i = 0; i < q; i++)
    {
        int pos = lwb(compress, mpp(a[x[i]], x[i])) - compress.begin() + 1;
        f.update(1, 1, sz, pos, pos, -x[i] - 1);
        f.update(1, 1, sz, pos, sz, 1);

        a[x[i]] = v[i];
        pos = lwb(compress, mpp(v[i], x[i])) - compress.begin() + 1;
        f.update(1, 1, sz, pos, pos, x[i] + 1);
        f.update(1, 1, sz, pos, sz, -1);
        ans[i] = f.query(1, 1, sz, 1, sz);
    }
    return ans;
}

#ifdef LOCAL
void solve()
{
    int n, q;
    cin >> n >> q;
    vi a(n), x(q), v(q);
    for (auto &x : a)
        cin >> x;
    for (int i = 0; i < q; i++)
    {
        cin >> x[i] >> v[i];
    }
    vi res = countScans(a, x, v);
    for (auto v : res)
        cout << v << el;
}

int32_t main()
{
    if (fopen((taskname + ".inp").c_str(), "r"))
    {
        freopen((taskname + ".inp").c_str(), "r", stdin);
        freopen((taskname + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tsc = 1;
    if (tc)
    {
        cin >> tsc;
    }
    while (tsc--)
    {
        solve();
        cout << el;
    }

    cerr << "\n"
         << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
#endif

Compilation message

bubblesort2.cpp: In function 'std::ostream& print_tuple_utils(std::ostream&, const T&)':
bubblesort2.cpp:137:8: warning: 'if constexpr' only available with '-std=c++17' or '-std=gnu++17'
  137 |     if constexpr (i == tuple_size<T>::value)
      |        ^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 580 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 3 ms 616 KB Output is correct
7 Correct 3 ms 616 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 580 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 580 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 576 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 580 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 3 ms 616 KB Output is correct
7 Correct 3 ms 616 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 580 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 580 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 576 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 15 ms 1320 KB Output is correct
20 Correct 13 ms 1472 KB Output is correct
21 Correct 13 ms 1472 KB Output is correct
22 Correct 13 ms 1492 KB Output is correct
23 Correct 17 ms 1364 KB Output is correct
24 Correct 12 ms 1364 KB Output is correct
25 Correct 12 ms 1364 KB Output is correct
26 Correct 13 ms 1472 KB Output is correct
27 Correct 12 ms 1364 KB Output is correct
28 Correct 12 ms 1348 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2008 KB Output is correct
2 Correct 54 ms 4052 KB Output is correct
3 Correct 98 ms 7172 KB Output is correct
4 Correct 97 ms 7200 KB Output is correct
5 Correct 102 ms 7208 KB Output is correct
6 Correct 93 ms 7264 KB Output is correct
7 Correct 105 ms 7232 KB Output is correct
8 Correct 92 ms 7288 KB Output is correct
9 Correct 92 ms 7156 KB Output is correct
10 Correct 77 ms 5184 KB Output is correct
11 Correct 76 ms 5180 KB Output is correct
12 Correct 76 ms 5220 KB Output is correct
13 Correct 90 ms 5184 KB Output is correct
14 Correct 73 ms 5252 KB Output is correct
15 Correct 72 ms 5184 KB Output is correct
16 Correct 68 ms 5164 KB Output is correct
17 Correct 70 ms 5172 KB Output is correct
18 Correct 69 ms 5220 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 580 KB Output is correct
5 Correct 3 ms 584 KB Output is correct
6 Correct 3 ms 616 KB Output is correct
7 Correct 3 ms 616 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 3 ms 580 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 580 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 576 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 4 ms 596 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 15 ms 1320 KB Output is correct
20 Correct 13 ms 1472 KB Output is correct
21 Correct 13 ms 1472 KB Output is correct
22 Correct 13 ms 1492 KB Output is correct
23 Correct 17 ms 1364 KB Output is correct
24 Correct 12 ms 1364 KB Output is correct
25 Correct 12 ms 1364 KB Output is correct
26 Correct 13 ms 1472 KB Output is correct
27 Correct 12 ms 1364 KB Output is correct
28 Correct 12 ms 1348 KB Output is correct
29 Correct 18 ms 2008 KB Output is correct
30 Correct 54 ms 4052 KB Output is correct
31 Correct 98 ms 7172 KB Output is correct
32 Correct 97 ms 7200 KB Output is correct
33 Correct 102 ms 7208 KB Output is correct
34 Correct 93 ms 7264 KB Output is correct
35 Correct 105 ms 7232 KB Output is correct
36 Correct 92 ms 7288 KB Output is correct
37 Correct 92 ms 7156 KB Output is correct
38 Correct 77 ms 5184 KB Output is correct
39 Correct 76 ms 5180 KB Output is correct
40 Correct 76 ms 5220 KB Output is correct
41 Correct 90 ms 5184 KB Output is correct
42 Correct 73 ms 5252 KB Output is correct
43 Correct 72 ms 5184 KB Output is correct
44 Correct 68 ms 5164 KB Output is correct
45 Correct 70 ms 5172 KB Output is correct
46 Correct 69 ms 5220 KB Output is correct
47 Correct 365 ms 26804 KB Output is correct
48 Correct 1525 ms 65048 KB Output is correct
49 Correct 1641 ms 67720 KB Output is correct
50 Correct 1630 ms 67640 KB Output is correct
51 Correct 1620 ms 67620 KB Output is correct
52 Correct 1609 ms 67632 KB Output is correct
53 Correct 1622 ms 67728 KB Output is correct
54 Correct 1491 ms 67884 KB Output is correct
55 Correct 1634 ms 67876 KB Output is correct
56 Correct 1517 ms 67764 KB Output is correct
57 Correct 1616 ms 67884 KB Output is correct
58 Correct 1501 ms 67836 KB Output is correct
59 Correct 1657 ms 66528 KB Output is correct
60 Correct 1537 ms 66440 KB Output is correct
61 Correct 1439 ms 66520 KB Output is correct
62 Correct 1338 ms 66312 KB Output is correct
63 Correct 1391 ms 66308 KB Output is correct
64 Correct 1267 ms 66348 KB Output is correct
65 Correct 1215 ms 66224 KB Output is correct
66 Correct 1209 ms 66172 KB Output is correct
67 Correct 1164 ms 66216 KB Output is correct