oj.uz

Submission #256500

# Submission time Handle Problem Language Result Execution time Memory
256500 2020-08-02T19:00:16 Z IgorI Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 3872 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 N = 1000002;

int tree[4 * N];
int valu[4 * N];
int push[4 * N];
int act[4 * N];

void Push(int V, int L, int M, int R)
{
    tree[2 * V + 1] += push[V];
    valu[2 * V + 1] += push[V];
    push[2 * V + 1] += push[V];
    tree[2 * V + 2] += push[V];
    valu[2 * V + 2] += push[V];
    push[2 * V + 2] += push[V];
    push[V] = 0;
    if (L + 1 == M && !act[2 * V + 1]) tree[2 * V + 1] = 0;
    if (M + 1 == R && !act[2 * V + 2]) tree[2 * V + 2] = 0;
}

void Active(int pos, int L = 0, int R = N, int V = 0)
{
    if (L + 1 == R)
    {
        act[V] ^= 1;
        if (act[V]) tree[V] = valu[V];
        else tree[V] = 0;
        return;
    }
    int M = (L + R) / 2;
    Push(V, L, M, R);
    if (pos < M) Active(pos, L, M, 2 * V + 1);
    else Active(pos, M, R, 2 * V + 2);
    tree[V] = max(tree[2 * V + 1], tree[2 * V + 2]);
}

void Add(int l, int r, int x, int L = 0, int R = N, int V = 0)
{
    if (l <= L && R <= r)
    {
        tree[V] += x;
        valu[V] += x;
        push[V] += x;
        if (L + 1 == R && !act[V]) tree[V] = 0;
        return;
    }
    if (R <= l || r <= L)
    {
        return;
    }
    int M = (L + R) / 2;
    Push(V, L, M, R);
    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]);
}

void Add2(int l, int r, int x)
{
    for (int i = l; i < r; i++) Add(i, i + 1, x);
}

int Get()
{
    return tree[0];
}

vi countScans(vi a, vi x, vi v)
{
    vector<pair<int, int> > elems;
    int n = a.size();
    int q = x.size();
    for (int i = 0; i < n; i++)
    {
        elems.push_back({a[i], i});
    }
    for (int i = 0; i < q; i++)
    {
        elems.push_back({v[i], x[i]});
    }
    uniq(elems);
    map<pii, int> mm;
    for (int i = 0; i < elems.size(); i++)
    {
        mm[elems[i]] = i;
    }
    for (int i = 0; i < elems.size(); i++)
    {
        Add2(i, i + 1, elems[i].second);
    }
    for (int i = 0; i < n; i++)
    {
        a[i] = mm[{a[i], i}];
        Active(a[i]);
        Add2(a[i] + 1, elems.size(), -1);
    }
    vi ans(q);
    for (int i = 0; i < q; i++)
    {
        int pos = x[i];
        Add2(a[pos] + 1, elems.size(), 1);
        Active(a[pos]);
        a[pos] = v[i];
        a[pos] = mm[{a[pos], pos}];
        Active(a[pos]);
        Add2(a[pos] + 1, elems.size(), -1);
        ans[i] = Get();
    }
    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

10 20
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
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 function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:113:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < elems.size(); i++)
                     ~~^~~~~~~~~~~~~~
bubblesort2.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < elems.size(); i++)
                     ~~^~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 760 KB Output is correct
2 Correct 640 ms 752 KB Output is correct
3 Correct 3254 ms 1144 KB Output is correct
4 Correct 3330 ms 1144 KB Output is correct
5 Correct 3262 ms 1132 KB Output is correct
6 Correct 3048 ms 1144 KB Output is correct
7 Correct 3097 ms 1144 KB Output is correct
8 Correct 3489 ms 1016 KB Output is correct
9 Correct 3520 ms 1016 KB Output is correct
10 Correct 3007 ms 960 KB Output is correct
11 Correct 2903 ms 1060 KB Output is correct
12 Correct 2880 ms 1016 KB Output is correct
13 Correct 3096 ms 936 KB Output is correct
14 Correct 3093 ms 1016 KB Output is correct
15 Correct 2890 ms 1024 KB Output is correct
16 Correct 2745 ms 912 KB Output is correct
17 Correct 3099 ms 1016 KB Output is correct
18 Correct 3035 ms 1040 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 760 KB Output is correct
2 Correct 640 ms 752 KB Output is correct
3 Correct 3254 ms 1144 KB Output is correct
4 Correct 3330 ms 1144 KB Output is correct
5 Correct 3262 ms 1132 KB Output is correct
6 Correct 3048 ms 1144 KB Output is correct
7 Correct 3097 ms 1144 KB Output is correct
8 Correct 3489 ms 1016 KB Output is correct
9 Correct 3520 ms 1016 KB Output is correct
10 Correct 3007 ms 960 KB Output is correct
11 Correct 2903 ms 1060 KB Output is correct
12 Correct 2880 ms 1016 KB Output is correct
13 Correct 3096 ms 936 KB Output is correct
14 Correct 3093 ms 1016 KB Output is correct
15 Correct 2890 ms 1024 KB Output is correct
16 Correct 2745 ms 912 KB Output is correct
17 Correct 3099 ms 1016 KB Output is correct
18 Correct 3035 ms 1040 KB Output is correct
19 Execution timed out 9086 ms 2248 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 9100 ms 3872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 760 KB Output is correct
2 Correct 640 ms 752 KB Output is correct
3 Correct 3254 ms 1144 KB Output is correct
4 Correct 3330 ms 1144 KB Output is correct
5 Correct 3262 ms 1132 KB Output is correct
6 Correct 3048 ms 1144 KB Output is correct
7 Correct 3097 ms 1144 KB Output is correct
8 Correct 3489 ms 1016 KB Output is correct
9 Correct 3520 ms 1016 KB Output is correct
10 Correct 3007 ms 960 KB Output is correct
11 Correct 2903 ms 1060 KB Output is correct
12 Correct 2880 ms 1016 KB Output is correct
13 Correct 3096 ms 936 KB Output is correct
14 Correct 3093 ms 1016 KB Output is correct
15 Correct 2890 ms 1024 KB Output is correct
16 Correct 2745 ms 912 KB Output is correct
17 Correct 3099 ms 1016 KB Output is correct
18 Correct 3035 ms 1040 KB Output is correct
19 Execution timed out 9086 ms 2248 KB Time limit exceeded
20 Halted 0 ms 0 KB -