oj.uz

Submission #256160

# Submission time Handle Problem Language Result Execution time Memory
256160 2020-08-02T10:40:42 Z IgorI Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 11104 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 = 350;

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 60 ms 384 KB Output is correct
2 Correct 101 ms 432 KB Output is correct
3 Correct 232 ms 504 KB Output is correct
4 Correct 244 ms 504 KB Output is correct
5 Correct 234 ms 508 KB Output is correct
6 Correct 199 ms 508 KB Output is correct
7 Correct 224 ms 504 KB Output is correct
8 Correct 225 ms 504 KB Output is correct
9 Correct 229 ms 504 KB Output is correct
10 Correct 213 ms 556 KB Output is correct
11 Correct 208 ms 504 KB Output is correct
12 Correct 212 ms 504 KB Output is correct
13 Correct 210 ms 504 KB Output is correct
14 Correct 200 ms 632 KB Output is correct
15 Correct 198 ms 512 KB Output is correct
16 Correct 194 ms 504 KB Output is correct
17 Correct 193 ms 504 KB Output is correct
18 Correct 191 ms 504 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 384 KB Output is correct
2 Correct 101 ms 432 KB Output is correct
3 Correct 232 ms 504 KB Output is correct
4 Correct 244 ms 504 KB Output is correct
5 Correct 234 ms 508 KB Output is correct
6 Correct 199 ms 508 KB Output is correct
7 Correct 224 ms 504 KB Output is correct
8 Correct 225 ms 504 KB Output is correct
9 Correct 229 ms 504 KB Output is correct
10 Correct 213 ms 556 KB Output is correct
11 Correct 208 ms 504 KB Output is correct
12 Correct 212 ms 504 KB Output is correct
13 Correct 210 ms 504 KB Output is correct
14 Correct 200 ms 632 KB Output is correct
15 Correct 198 ms 512 KB Output is correct
16 Correct 194 ms 504 KB Output is correct
17 Correct 193 ms 504 KB Output is correct
18 Correct 191 ms 504 KB Output is correct
19 Correct 862 ms 872 KB Output is correct
20 Correct 973 ms 896 KB Output is correct
21 Correct 943 ms 896 KB Output is correct
22 Correct 966 ms 932 KB Output is correct
23 Correct 850 ms 932 KB Output is correct
24 Correct 875 ms 928 KB Output is correct
25 Correct 799 ms 1016 KB Output is correct
26 Correct 817 ms 1016 KB Output is correct
27 Correct 778 ms 932 KB Output is correct
28 Correct 766 ms 896 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1697 ms 1812 KB Output is correct
2 Correct 4489 ms 2892 KB Output is correct
3 Correct 8064 ms 3924 KB Output is correct
4 Correct 7767 ms 3832 KB Output is correct
5 Correct 7664 ms 3916 KB Output is correct
6 Correct 7535 ms 3920 KB Output is correct
7 Correct 6860 ms 3840 KB Output is correct
8 Correct 6967 ms 3832 KB Output is correct
9 Correct 7096 ms 3832 KB Output is correct
10 Correct 4830 ms 3920 KB Output is correct
11 Correct 5021 ms 3840 KB Output is correct
12 Correct 5325 ms 3840 KB Output is correct
13 Correct 5015 ms 3920 KB Output is correct
14 Correct 5193 ms 3832 KB Output is correct
15 Correct 5092 ms 3920 KB Output is correct
16 Correct 5068 ms 3920 KB Output is correct
17 Correct 5217 ms 3920 KB Output is correct
18 Correct 5373 ms 3924 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 384 KB Output is correct
2 Correct 101 ms 432 KB Output is correct
3 Correct 232 ms 504 KB Output is correct
4 Correct 244 ms 504 KB Output is correct
5 Correct 234 ms 508 KB Output is correct
6 Correct 199 ms 508 KB Output is correct
7 Correct 224 ms 504 KB Output is correct
8 Correct 225 ms 504 KB Output is correct
9 Correct 229 ms 504 KB Output is correct
10 Correct 213 ms 556 KB Output is correct
11 Correct 208 ms 504 KB Output is correct
12 Correct 212 ms 504 KB Output is correct
13 Correct 210 ms 504 KB Output is correct
14 Correct 200 ms 632 KB Output is correct
15 Correct 198 ms 512 KB Output is correct
16 Correct 194 ms 504 KB Output is correct
17 Correct 193 ms 504 KB Output is correct
18 Correct 191 ms 504 KB Output is correct
19 Correct 862 ms 872 KB Output is correct
20 Correct 973 ms 896 KB Output is correct
21 Correct 943 ms 896 KB Output is correct
22 Correct 966 ms 932 KB Output is correct
23 Correct 850 ms 932 KB Output is correct
24 Correct 875 ms 928 KB Output is correct
25 Correct 799 ms 1016 KB Output is correct
26 Correct 817 ms 1016 KB Output is correct
27 Correct 778 ms 932 KB Output is correct
28 Correct 766 ms 896 KB Output is correct
29 Correct 1697 ms 1812 KB Output is correct
30 Correct 4489 ms 2892 KB Output is correct
31 Correct 8064 ms 3924 KB Output is correct
32 Correct 7767 ms 3832 KB Output is correct
33 Correct 7664 ms 3916 KB Output is correct
34 Correct 7535 ms 3920 KB Output is correct
35 Correct 6860 ms 3840 KB Output is correct
36 Correct 6967 ms 3832 KB Output is correct
37 Correct 7096 ms 3832 KB Output is correct
38 Correct 4830 ms 3920 KB Output is correct
39 Correct 5021 ms 3840 KB Output is correct
40 Correct 5325 ms 3840 KB Output is correct
41 Correct 5015 ms 3920 KB Output is correct
42 Correct 5193 ms 3832 KB Output is correct
43 Correct 5092 ms 3920 KB Output is correct
44 Correct 5068 ms 3920 KB Output is correct
45 Correct 5217 ms 3920 KB Output is correct
46 Correct 5373 ms 3924 KB Output is correct
47 Execution timed out 9071 ms 11104 KB Time limit exceeded
48 Halted 0 ms 0 KB -