oj.uz

Submission #256156

# Submission time Handle Problem Language Result Execution time Memory
256156 2020-08-02T10:36:50 Z IgorI Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 1792 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

const int INF = 1e9 + 7;
const int K = 4000;

struct Element{
    int x;
    int pos_order;
    int sp;
};

struct SegTree{
    vector<int> tree;
    vector<int> push;
    SegTree()
    {
        tree.resize(4 * K);
        push.resize(4 * K);
    }
    void Push(int V)
    {
        tree[2 * V + 1] += push[V];
        push[2 * V + 1] += push[V];
        tree[2 * V + 2] += push[V];
        push[2 * V + 2] += push[V];
        push[V] = 0;
    }
    void __Add(int l, int r, int x, int L, int R, int V)
    {
        if (l <= L && R <= r)
        {
            tree[V] += x;
            push[V] += x;
            return;
        }
        if (r <= L || R <= l)
        {
            return;
        }
        int M = (L + R) / 2;
        Push(V);
        __Add(l, r, x, L, M, 2 * V + 1);
        __Add(l, r, x, M, R, 2 * V + 2);
        tree[V] = max(tree[2 * V + 1], tree[2 * V + 2]);
    }
    int Add(int l, int r, int x)
    {
        __Add(l, r, x, 0, K, 0);
    }
    int __Get(int l, int r, int L, int R, int V)
    {
        if (l <= L && R <= r)
        {
            return tree[V];
        }
        if (r <= L || R <= l)
        {
            return 0;
        }
        int M = (L + R) / 2;
        Push(V);
        return max(__Get(l, r, L, M, 2 * V + 1), __Get(l, r, M, R, 2 * V + 2));
    }
    int Get(int l, int r)
    {
        return __Get(l, r, 0, K, 0);
    }
    void build(int L, int R, int V, vector<Element> &val)
    {
        if (L + 1 == R)
        {
            tree[V] = val[L].sp;
            push[V] = 0;
            return;
        }
        int M = (L + R) / 2;
        build(L, M, 2 * V + 1, val);
        build(M, R, 2 * V + 2, val);
        push[V] = 0;
        tree[V] = max(tree[2 * V + 1], tree[2 * V + 2]);
    }
};

bool order(Element a, Element b)
{
    return a.pos_order < b.pos_order;
}

bool sorted(Element a, Element b)
{
    return a.x < b.x;
}

struct Block{
    SegTree d;
    vector<Element> a;
    Block()
    {
        a.resize(K);
        for (int i = 0; i < K; i++)
        {
            a[i].x = INF;
            a[i].pos_order = i;
        }
    }
    int cntmore(int x)
    {
        int L = -1, R = a.size();
        while (L + 1 < R)
        {
            int M = (L + R) / 2;
            if (a[M].x > x)
                R = M;
            else
                L = M;
        }
        return K - R;
    }
    void change(int pos_in_block, int initial, int A)
    {
        for (int i = 0; i < K; i++)
        {
            a[i].sp = d.Get(i, i + 1);
        }
        sort(all(a), order);
        int Z = a[pos_in_block].x;
        a[pos_in_block].x = A;
        for (int i = 0; i < pos_in_block; i++)
        {
            if (a[i].x > a[pos_in_block].x) initial++;
        }
        a[pos_in_block].sp = initial;
        for (int i = pos_in_block + 1; i < K; i++)
        {
            a[i].sp -= Z > a[i].x;
            a[i].sp += A > a[i].x;
        }
        sort(all(a), sorted);
        d.build(0, K, 0, a);
    }
    void query(int x, int val)
    {
        int L = -1, R = K;
        while (L + 1 < R)
        {
            int M = (L + R) / 2;
            if (a[M].x < x)
                L = M;
            else
                R = M;
        }
        d.Add(0, L + 1, val);
    }
};

vi countScans(vi a, vi x, vi v)
{
    int n = a.size(), q = x.size();
    vi ans(q);
    vector<Block> data(n / K + 1);
    for (int i = 0; i < n; i++)
    {
        int bl = i / K;
        int ps = i % K;
        int initial = 0;
        for (int j = 0; j < bl; j++) initial += data[j].cntmore(a[i]);
        data[bl].change(ps, initial, a[i]);
    }
    for (int i = 0; i < q; i++)
    {
        int bl = x[i] / K;
        int ps = x[i] % K;
        int initial = 0;
        for (int j = 0; j < bl; j++) initial += data[j].cntmore(v[i]);
        data[bl].change(ps, initial, v[i]);
        int fr = a[x[i]];
        int to = v[i];
        a[x[i]] = v[i];
        for (int j = bl + 1; j < n / K + 1; j++) data[j].query(fr, -1);
        for (int j = bl + 1; j < n / K + 1; j++) data[j].query(to, 1);
        int answer = 0;
        for (int j = 0; j < n / K + 1; j++) answer = max(answer, data[j].d.Get(0, K));
        ans[i] = answer;
        #ifdef LOCAL
        cout << "after i = " << i << endl;
        for (int j = 0; j < n / K + 1; j++)
        {
            cout << j << ": " << endl;
            for (int i = 0; i < K; i++) cout << data[j].a[i].x << " ";
            cout << endl;
            for (int i = 0; i < K; i++) cout << data[j].d.Get(i, i + 1) << " ";
            cout << endl;
        }
        #endif // LOCAL
    }
    return ans;
}

#ifdef LOCAL
signed main()
{
    int n, q;
    cin >> n >> q;
    vi a(n), x(q), v(q);
    forn(i, n) cin >> a[i];
    forn(i, q) cin >> x[i] >> v[i];
    vi ans = countScans(a, x, v);
    forn(i, q) cout << ans[i] << "\n";
}
#endif // LOCAL

/*
10 10
1 2 3 4 5 1 2 3 4 5
0 10
1 9
2 8
3 7
4 6
5 5
6 4
7 3
8 2
9 1
*/

Compilation message

bubblesort2.cpp: In member function 'int SegTree::Add(int, int, int)':
bubblesort2.cpp:77:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 632 KB Output is correct
2 Correct 1393 ms 632 KB Output is correct
3 Correct 3528 ms 584 KB Output is correct
4 Correct 3533 ms 592 KB Output is correct
5 Correct 3605 ms 588 KB Output is correct
6 Correct 3396 ms 588 KB Output is correct
7 Correct 3441 ms 592 KB Output is correct
8 Correct 3587 ms 592 KB Output is correct
9 Correct 3607 ms 552 KB Output is correct
10 Correct 3597 ms 584 KB Output is correct
11 Correct 3739 ms 588 KB Output is correct
12 Correct 3626 ms 588 KB Output is correct
13 Correct 3633 ms 544 KB Output is correct
14 Correct 3613 ms 588 KB Output is correct
15 Correct 3716 ms 632 KB Output is correct
16 Correct 3508 ms 632 KB Output is correct
17 Correct 3493 ms 512 KB Output is correct
18 Correct 3556 ms 632 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 632 KB Output is correct
2 Correct 1393 ms 632 KB Output is correct
3 Correct 3528 ms 584 KB Output is correct
4 Correct 3533 ms 592 KB Output is correct
5 Correct 3605 ms 588 KB Output is correct
6 Correct 3396 ms 588 KB Output is correct
7 Correct 3441 ms 592 KB Output is correct
8 Correct 3587 ms 592 KB Output is correct
9 Correct 3607 ms 552 KB Output is correct
10 Correct 3597 ms 584 KB Output is correct
11 Correct 3739 ms 588 KB Output is correct
12 Correct 3626 ms 588 KB Output is correct
13 Correct 3633 ms 544 KB Output is correct
14 Correct 3613 ms 588 KB Output is correct
15 Correct 3716 ms 632 KB Output is correct
16 Correct 3508 ms 632 KB Output is correct
17 Correct 3493 ms 512 KB Output is correct
18 Correct 3556 ms 632 KB Output is correct
19 Execution timed out 9071 ms 896 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9090 ms 1792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 632 KB Output is correct
2 Correct 1393 ms 632 KB Output is correct
3 Correct 3528 ms 584 KB Output is correct
4 Correct 3533 ms 592 KB Output is correct
5 Correct 3605 ms 588 KB Output is correct
6 Correct 3396 ms 588 KB Output is correct
7 Correct 3441 ms 592 KB Output is correct
8 Correct 3587 ms 592 KB Output is correct
9 Correct 3607 ms 552 KB Output is correct
10 Correct 3597 ms 584 KB Output is correct
11 Correct 3739 ms 588 KB Output is correct
12 Correct 3626 ms 588 KB Output is correct
13 Correct 3633 ms 544 KB Output is correct
14 Correct 3613 ms 588 KB Output is correct
15 Correct 3716 ms 632 KB Output is correct
16 Correct 3508 ms 632 KB Output is correct
17 Correct 3493 ms 512 KB Output is correct
18 Correct 3556 ms 632 KB Output is correct
19 Execution timed out 9071 ms 896 KB Time limit exceeded
20 Halted 0 ms 0 KB -