oj.uz

Submission #469520

# Submission time Handle Problem Language Result Execution time Memory
469520 2021-09-01T08:43:20 Z Lam_lai_cuoc_doi Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 682 ms 493968 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr int Inf = 1e9 + 7;

struct FenwickTree
{
    int a[N];
    int n;
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    int Get(int p)
    {
        int ans(0);
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }
} g;

struct SegmentTree
{
    int n;
    int lazy[N * 8], st[N * 8];

    SegmentTree()
    {
        memset(lazy, 0, sizeof lazy);
        fill_n(st, N * 8, -Inf);
    }
    void Push(int id)
    {
        if (lazy[id] != 0)
        {
            if (st[id << 1] != -Inf)
                st[id << 1] += lazy[id];
            lazy[id << 1] += lazy[id];
            if (st[id << 1 | 1] != -Inf)
                st[id << 1 | 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
            lazy[id] = 0;
        }
    }
    void Update(int id, int l, int r, const int &x, const int &v)
    {
        if (l > x || r < x)
            return;
        if (l == x && r == x)
        {
            st[id] = v;
            return;
        }
        Push(id);
        Update(id << 1, l, (l + r) / 2, x, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int x, int v)
    {
        Update(1, 1, n, x, v);
    }
    void Update(int id, int l, int r, const int &a, const int &b, const int &v)
    {
        if (l > b || r < a)
            return;
        if (l >= a && r <= b)
        {
            st[id] += v;
            lazy[id] += v;
            return;
        }
        Push(id);
        Update(id << 1, l, (l + r) / 2, a, b, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int l, int r, int v)
    {
        Update(1, 1, n, l, r, v);
    }
} f;

vector<int> s;
set<int> pos[N * 8];
int n, m;

#define Find(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin() + 1)

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v)
{
    vector<int> ans(x.size(), 0);

    n = a.size();
    m = x.size();

    for (int i = 0; i < n; ++i)
        s.emplace_back(a[i]);
    for (int i = 0; i < m; ++i)
        s.emplace_back(v[i]);

    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
    f.n = g.n = s.size();

    for (int i = 0; i < n; ++i)
    {
        a[i] = Find(s, a[i]);
        g.Update(a[i], 1);
        pos[a[i]].insert(i);
    }

    for (int i = 0; i < (int)s.size(); ++i)
        if (!pos[i + 1].empty())
            f.Update(i + 1, *pos[i + 1].rbegin() + 1 - g.Get(i + 1));

    for (int i = 0; i < m; ++i)
    {
        v[i] = Find(s, v[i]);

        pos[a[x[i]]].erase(x[i]);
        f.Update(a[x[i]], s.size(), 1);
        g.Update(a[x[i]], -1);

        if (pos[a[x[i]]].empty())
            f.Update(a[x[i]], -Inf);
        else
            f.Update(a[x[i]], *pos[a[x[i]]].rbegin() + 1 - g.Get(a[x[i]]));

        a[x[i]] = v[i];

        pos[a[x[i]]].insert(x[i]);
        f.Update(a[x[i]], s.size(), -1);
        g.Update(a[x[i]], 1);
        f.Update(v[i], *pos[v[i]].rbegin() + 1 - g.Get(v[i]));

        ans[i] = f.st[1];
    }

    return ans;
}

Compilation message

bubblesort2.cpp: In function 'void read(T&)':
bubblesort2.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 221472 KB Output is correct
2 Correct 124 ms 221476 KB Output is correct
3 Correct 128 ms 221576 KB Output is correct
4 Correct 126 ms 221636 KB Output is correct
5 Correct 124 ms 221608 KB Output is correct
6 Correct 125 ms 221632 KB Output is correct
7 Correct 122 ms 221632 KB Output is correct
8 Correct 126 ms 221624 KB Output is correct
9 Correct 123 ms 221600 KB Output is correct
10 Correct 123 ms 221524 KB Output is correct
11 Correct 125 ms 221684 KB Output is correct
12 Correct 124 ms 221608 KB Output is correct
13 Correct 124 ms 221508 KB Output is correct
14 Correct 125 ms 221624 KB Output is correct
15 Correct 123 ms 221608 KB Output is correct
16 Correct 123 ms 221508 KB Output is correct
17 Correct 123 ms 221508 KB Output is correct
18 Correct 123 ms 221508 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 221472 KB Output is correct
2 Correct 124 ms 221476 KB Output is correct
3 Correct 128 ms 221576 KB Output is correct
4 Correct 126 ms 221636 KB Output is correct
5 Correct 124 ms 221608 KB Output is correct
6 Correct 125 ms 221632 KB Output is correct
7 Correct 122 ms 221632 KB Output is correct
8 Correct 126 ms 221624 KB Output is correct
9 Correct 123 ms 221600 KB Output is correct
10 Correct 123 ms 221524 KB Output is correct
11 Correct 125 ms 221684 KB Output is correct
12 Correct 124 ms 221608 KB Output is correct
13 Correct 124 ms 221508 KB Output is correct
14 Correct 125 ms 221624 KB Output is correct
15 Correct 123 ms 221608 KB Output is correct
16 Correct 123 ms 221508 KB Output is correct
17 Correct 123 ms 221508 KB Output is correct
18 Correct 123 ms 221508 KB Output is correct
19 Correct 136 ms 222196 KB Output is correct
20 Correct 136 ms 222276 KB Output is correct
21 Correct 137 ms 222308 KB Output is correct
22 Correct 136 ms 222212 KB Output is correct
23 Correct 139 ms 222272 KB Output is correct
24 Correct 138 ms 222196 KB Output is correct
25 Correct 138 ms 222188 KB Output is correct
26 Correct 134 ms 222148 KB Output is correct
27 Correct 136 ms 222176 KB Output is correct
28 Correct 136 ms 222308 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 223076 KB Output is correct
2 Correct 168 ms 224660 KB Output is correct
3 Correct 214 ms 226148 KB Output is correct
4 Correct 205 ms 226092 KB Output is correct
5 Correct 208 ms 226100 KB Output is correct
6 Correct 214 ms 226184 KB Output is correct
7 Correct 200 ms 226020 KB Output is correct
8 Correct 209 ms 226040 KB Output is correct
9 Correct 203 ms 226108 KB Output is correct
10 Correct 191 ms 226176 KB Output is correct
11 Correct 184 ms 226108 KB Output is correct
12 Correct 184 ms 226084 KB Output is correct
13 Correct 187 ms 226240 KB Output is correct
14 Correct 189 ms 226108 KB Output is correct
15 Correct 183 ms 226100 KB Output is correct
16 Correct 182 ms 226236 KB Output is correct
17 Correct 178 ms 226236 KB Output is correct
18 Correct 182 ms 226044 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 221472 KB Output is correct
2 Correct 124 ms 221476 KB Output is correct
3 Correct 128 ms 221576 KB Output is correct
4 Correct 126 ms 221636 KB Output is correct
5 Correct 124 ms 221608 KB Output is correct
6 Correct 125 ms 221632 KB Output is correct
7 Correct 122 ms 221632 KB Output is correct
8 Correct 126 ms 221624 KB Output is correct
9 Correct 123 ms 221600 KB Output is correct
10 Correct 123 ms 221524 KB Output is correct
11 Correct 125 ms 221684 KB Output is correct
12 Correct 124 ms 221608 KB Output is correct
13 Correct 124 ms 221508 KB Output is correct
14 Correct 125 ms 221624 KB Output is correct
15 Correct 123 ms 221608 KB Output is correct
16 Correct 123 ms 221508 KB Output is correct
17 Correct 123 ms 221508 KB Output is correct
18 Correct 123 ms 221508 KB Output is correct
19 Correct 136 ms 222196 KB Output is correct
20 Correct 136 ms 222276 KB Output is correct
21 Correct 137 ms 222308 KB Output is correct
22 Correct 136 ms 222212 KB Output is correct
23 Correct 139 ms 222272 KB Output is correct
24 Correct 138 ms 222196 KB Output is correct
25 Correct 138 ms 222188 KB Output is correct
26 Correct 134 ms 222148 KB Output is correct
27 Correct 136 ms 222176 KB Output is correct
28 Correct 136 ms 222308 KB Output is correct
29 Correct 134 ms 223076 KB Output is correct
30 Correct 168 ms 224660 KB Output is correct
31 Correct 214 ms 226148 KB Output is correct
32 Correct 205 ms 226092 KB Output is correct
33 Correct 208 ms 226100 KB Output is correct
34 Correct 214 ms 226184 KB Output is correct
35 Correct 200 ms 226020 KB Output is correct
36 Correct 209 ms 226040 KB Output is correct
37 Correct 203 ms 226108 KB Output is correct
38 Correct 191 ms 226176 KB Output is correct
39 Correct 184 ms 226108 KB Output is correct
40 Correct 184 ms 226084 KB Output is correct
41 Correct 187 ms 226240 KB Output is correct
42 Correct 189 ms 226108 KB Output is correct
43 Correct 183 ms 226100 KB Output is correct
44 Correct 182 ms 226236 KB Output is correct
45 Correct 178 ms 226236 KB Output is correct
46 Correct 182 ms 226044 KB Output is correct
47 Correct 676 ms 235484 KB Output is correct
48 Runtime error 682 ms 493968 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -