oj.uz

Submission #835016

# Submission time Handle Problem Language Result Execution time Memory
835016 2023-08-23T05:54:18 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 1767 ms 67972 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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 3 ms 596 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 2 ms 340 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 3 ms 596 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 13 ms 1336 KB Output is correct
20 Correct 14 ms 1480 KB Output is correct
21 Correct 13 ms 1492 KB Output is correct
22 Correct 14 ms 1492 KB Output is correct
23 Correct 13 ms 1364 KB Output is correct
24 Correct 13 ms 1364 KB Output is correct
25 Correct 13 ms 1364 KB Output is correct
26 Correct 13 ms 1364 KB Output is correct
27 Correct 13 ms 1364 KB Output is correct
28 Correct 13 ms 1364 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 55 ms 4044 KB Output is correct
3 Correct 98 ms 7232 KB Output is correct
4 Correct 97 ms 7220 KB Output is correct
5 Correct 101 ms 7224 KB Output is correct
6 Correct 95 ms 7280 KB Output is correct
7 Correct 105 ms 7268 KB Output is correct
8 Correct 96 ms 7248 KB Output is correct
9 Correct 95 ms 7268 KB Output is correct
10 Correct 80 ms 5284 KB Output is correct
11 Correct 77 ms 5184 KB Output is correct
12 Correct 82 ms 5300 KB Output is correct
13 Correct 76 ms 5184 KB Output is correct
14 Correct 90 ms 5184 KB Output is correct
15 Correct 76 ms 5184 KB Output is correct
16 Correct 70 ms 5244 KB Output is correct
17 Correct 71 ms 5184 KB Output is correct
18 Correct 70 ms 5184 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 3 ms 596 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 13 ms 1336 KB Output is correct
20 Correct 14 ms 1480 KB Output is correct
21 Correct 13 ms 1492 KB Output is correct
22 Correct 14 ms 1492 KB Output is correct
23 Correct 13 ms 1364 KB Output is correct
24 Correct 13 ms 1364 KB Output is correct
25 Correct 13 ms 1364 KB Output is correct
26 Correct 13 ms 1364 KB Output is correct
27 Correct 13 ms 1364 KB Output is correct
28 Correct 13 ms 1364 KB Output is correct
29 Correct 18 ms 2008 KB Output is correct
30 Correct 55 ms 4044 KB Output is correct
31 Correct 98 ms 7232 KB Output is correct
32 Correct 97 ms 7220 KB Output is correct
33 Correct 101 ms 7224 KB Output is correct
34 Correct 95 ms 7280 KB Output is correct
35 Correct 105 ms 7268 KB Output is correct
36 Correct 96 ms 7248 KB Output is correct
37 Correct 95 ms 7268 KB Output is correct
38 Correct 80 ms 5284 KB Output is correct
39 Correct 77 ms 5184 KB Output is correct
40 Correct 82 ms 5300 KB Output is correct
41 Correct 76 ms 5184 KB Output is correct
42 Correct 90 ms 5184 KB Output is correct
43 Correct 76 ms 5184 KB Output is correct
44 Correct 70 ms 5244 KB Output is correct
45 Correct 71 ms 5184 KB Output is correct
46 Correct 70 ms 5184 KB Output is correct
47 Correct 374 ms 26824 KB Output is correct
48 Correct 1515 ms 65064 KB Output is correct
49 Correct 1767 ms 67696 KB Output is correct
50 Correct 1655 ms 67640 KB Output is correct
51 Correct 1655 ms 67632 KB Output is correct
52 Correct 1651 ms 67624 KB Output is correct
53 Correct 1715 ms 67700 KB Output is correct
54 Correct 1526 ms 67912 KB Output is correct
55 Correct 1587 ms 67968 KB Output is correct
56 Correct 1477 ms 67756 KB Output is correct
57 Correct 1611 ms 67876 KB Output is correct
58 Correct 1519 ms 67972 KB Output is correct
59 Correct 1383 ms 66528 KB Output is correct
60 Correct 1365 ms 66500 KB Output is correct
61 Correct 1318 ms 66560 KB Output is correct
62 Correct 1276 ms 66344 KB Output is correct
63 Correct 1286 ms 66308 KB Output is correct
64 Correct 1306 ms 66308 KB Output is correct
65 Correct 1205 ms 66200 KB Output is correct
66 Correct 1197 ms 66216 KB Output is correct
67 Correct 1226 ms 66188 KB Output is correct