oj.uz

Submission #256100

# Submission time Handle Problem Language Result Execution time Memory
256100 2020-08-02T09:49:17 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 = 2200;

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(M);
        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(a[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;
    }
    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

/*
4 2
1 2 3 4
0 3
2 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 466 ms 504 KB Output is correct
2 Correct 688 ms 384 KB Output is correct
3 Correct 1978 ms 512 KB Output is correct
4 Correct 2141 ms 632 KB Output is correct
5 Correct 1913 ms 556 KB Output is correct
6 Correct 1866 ms 632 KB Output is correct
7 Correct 1872 ms 632 KB Output is correct
8 Correct 1929 ms 560 KB Output is correct
9 Correct 2000 ms 632 KB Output is correct
10 Correct 2152 ms 548 KB Output is correct
11 Correct 2131 ms 544 KB Output is correct
12 Correct 2058 ms 552 KB Output is correct
13 Correct 2023 ms 548 KB Output is correct
14 Correct 2089 ms 548 KB Output is correct
15 Correct 2137 ms 544 KB Output is correct
16 Correct 2310 ms 548 KB Output is correct
17 Correct 2248 ms 544 KB Output is correct
18 Correct 2103 ms 544 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 504 KB Output is correct
2 Correct 688 ms 384 KB Output is correct
3 Correct 1978 ms 512 KB Output is correct
4 Correct 2141 ms 632 KB Output is correct
5 Correct 1913 ms 556 KB Output is correct
6 Correct 1866 ms 632 KB Output is correct
7 Correct 1872 ms 632 KB Output is correct
8 Correct 1929 ms 560 KB Output is correct
9 Correct 2000 ms 632 KB Output is correct
10 Correct 2152 ms 548 KB Output is correct
11 Correct 2131 ms 544 KB Output is correct
12 Correct 2058 ms 552 KB Output is correct
13 Correct 2023 ms 548 KB Output is correct
14 Correct 2089 ms 548 KB Output is correct
15 Correct 2137 ms 544 KB Output is correct
16 Correct 2310 ms 548 KB Output is correct
17 Correct 2248 ms 544 KB Output is correct
18 Correct 2103 ms 544 KB Output is correct
19 Incorrect 7200 ms 1104 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9096 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 466 ms 504 KB Output is correct
2 Correct 688 ms 384 KB Output is correct
3 Correct 1978 ms 512 KB Output is correct
4 Correct 2141 ms 632 KB Output is correct
5 Correct 1913 ms 556 KB Output is correct
6 Correct 1866 ms 632 KB Output is correct
7 Correct 1872 ms 632 KB Output is correct
8 Correct 1929 ms 560 KB Output is correct
9 Correct 2000 ms 632 KB Output is correct
10 Correct 2152 ms 548 KB Output is correct
11 Correct 2131 ms 544 KB Output is correct
12 Correct 2058 ms 552 KB Output is correct
13 Correct 2023 ms 548 KB Output is correct
14 Correct 2089 ms 548 KB Output is correct
15 Correct 2137 ms 544 KB Output is correct
16 Correct 2310 ms 548 KB Output is correct
17 Correct 2248 ms 544 KB Output is correct
18 Correct 2103 ms 544 KB Output is correct
19 Incorrect 7200 ms 1104 KB Output isn't correct
20 Halted 0 ms 0 KB -