oj.uz

Submission #1093900

# Submission time Handle Problem Language Result Execution time Memory
1093900 2024-09-28T04:18:25 Z anhthi Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 120 ms 191072 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }

template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }

template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }

int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}

const ll oo = (ll) 1e17;
const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7;

const int mxn = 1e6 + 5, LOG = 50;

void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

struct Seg {
    int n;
    vector<int> st, lz;

    Seg(int n) : n(n) {
        lz.resize(n << 2); st.resize(n << 2);
    }

    void setOne(int i, int d) {
        st[i] += d;
        lz[i] += d;
    }

    void down(int i) {
        if (!lz[i])
            return;
        setOne(2 * i, lz[i]);
        setOne(2 * i + 1, lz[i]);
        lz[i] = 0;
    }

    void upd(int i, int l, int r, int u, int v, int d) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            return setOne(i, d);
        }
        down(i);
        int m = (l + r) >> 1;
        upd(2 * i, l, m, u, v, d);
        upd(2 * i + 1, m + 1, r, u, v, d);

        st[i] = max(st[2 * i], st[2 * i + 1]);
    }

    void upd(int u, int v, int d) {
        if (u > v) return;
        return upd(1, 1, n, u, v, d);
    }

    void change(int p, int val) {
        int i = 1;
        for (int l = 1, r = n; l < r; ) {
            down(i);
            int m = (l + r) >> 1;
            if (p > m) {
                l = m + 1;
                i = 2 * i + 1;
            }
            else {
                r = m;
                i = 2 * i;
            }
        }
        st[i] = val;
        while (i > 1) {
            i >>= 1;
            st[i] = max(st[2 * i], st[2 * i + 1]);
        }
    }

    int get(int i, int l, int r, int u, int v) {
        if (l > v || r < u) return -inf;
        if (l >= u && r <= v) return st[i];
        down(i);
        int m = (l + r) >> 1;
        return max(get(2 * i, l, m, u, v), get(2 * i + 1, m + 1, r, u, v));
    }

    int get() {
        return st[1];
    }
};

set<int> s[mxn << 1];

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){

    int n = sz(A), q = sz(X);

    vector<int> cps;
    for (int i : A) cps.pb(i);
    for (int i : V) cps.pb(i);

    compress(cps);
    for (int &i : A) i = lower_bound(all(cps), i) - cps.begin() + 1;
    for (int &i : V) i = lower_bound(all(cps), i) - cps.begin() + 1;

    int m = sz(cps);
    forn(i, 0, n - 1) {
        s[A[i]].insert(i + 1);
    }
    Seg seg(m);
    forn(i, 1, m) {
        seg.upd(i, i, *s[i].rbegin());
        seg.upd(i, m, -sz(s[i]));
    }

    vector<int> ans(q);
    forn(i, 0, q - 1) {
        int p = X[i];
        int value = V[i];

        seg.upd(A[p], m, +1);
        seg.upd(A[p], A[p], -(*s[A[p]].rbegin()));
        s[A[p]].erase(p + 1);
        if (sz(s[A[p]])) seg.upd(A[p], A[p], *s[A[p]].rbegin());

        A[p] = value;

        seg.upd(A[p], m, -1);
        if (sz(s[A[p]])) seg.upd(A[p], A[p], -(*s[A[p]].rbegin()));
        s[A[p]].insert(p + 1);
        seg.upd(A[p], A[p], *s[A[p]].rbegin());

        ans[i] = seg.get();
    }

    return ans;
}

//int main(void) {
//
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    #define TASK "cquery"
//    if (fopen(TASK".inp", "r")) {
//        freopen(TASK".inp", "r", stdin);
//        freopen(TASK".out", "w", stdout);
//    }
//
//    vector<int> A = {1, 2, 3, 4};
//    vector<int> X = {0, 2};
//    vector<int> V = {3, 1};
//
//    for (int val : countScans(A, X, V))
//        cout << val << '\n';
//
//    return 0;
//}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 191072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 191072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 96084 KB Output is correct
2 Correct 77 ms 97500 KB Output is correct
3 Correct 106 ms 99016 KB Output is correct
4 Correct 110 ms 99016 KB Output is correct
5 Correct 105 ms 99020 KB Output is correct
6 Correct 107 ms 98832 KB Output is correct
7 Correct 106 ms 99016 KB Output is correct
8 Correct 110 ms 98888 KB Output is correct
9 Correct 106 ms 99020 KB Output is correct
10 Correct 95 ms 99016 KB Output is correct
11 Correct 89 ms 99020 KB Output is correct
12 Correct 84 ms 99016 KB Output is correct
13 Correct 81 ms 99020 KB Output is correct
14 Correct 80 ms 99020 KB Output is correct
15 Correct 94 ms 99028 KB Output is correct
16 Correct 77 ms 98864 KB Output is correct
17 Correct 77 ms 99016 KB Output is correct
18 Correct 77 ms 99016 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 191072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -