#include "bubblesort2.h"
#include <set>
#include <algorithm>
using namespace std;
static int stupid(vector<int> A)
{
int res = 0;
int n = A.size();
while (true)
{
bool was = false;
for (int i = 1; i < n; ++i)
{
if (A[i-1] > A[i])
{
swap(A[i-1], A[i]);
was = true;
}
}
if (was)
++res;
else
break;
}
return res;
}
static int get(vector<int> &f, int x)
{
int res = 0;
for (; x >= 0; x = (x&(x+1))-1)
res += f[x];
return res;
}
static void add(vector<int> &f, int x, int v)
{
for (; x < f.size(); x |= (x+1))
f[x] += v;
}
static int stupid1(vector<int> A)
{
int n = A.size();
int res = 0;
for (int i = 1; i < n; ++i)
{
int c = 0;
for (int j = 0; j < i; ++j)
if (A[i] < A[j])
++c;
res = max(res, c);
}
return res;
}
static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
{
int n = A.size();
int res = 0;
for (int i = 0; i < n; ++i)
{
res = max(res, i - get(F, A[i]));
add(F, A[i], 1);
}
for (int i = 0; i < n; ++i)
add(F, A[i], -1);
return res;
}
static int smart1(const vector<int> &A)
{
int n = A.size();
int res = 0;
int p = int(2e9);
for (int i = n - 1; i > 0; --i)
{
if (A[i] < p)
{
p = A[i];
int c = 0;
for (int j = 0; j < i; ++j)
if (A[i] < A[j])
++c;
res = max(res, c);
}
}
return res;
}
void merge(vector<int> &res, const vector<int> &a, const vector<int> &b)
{
int i, j, k;
res.resize(a.size()+b.size());
k = 0;
for (i = 0, j = 0; i < a.size() && j < b.size(); )
{
if (a[i] < b[j])
res[k++] = a[i++];
else
res[k++] = b[j++];
}
for (; i < a.size(); ++i, ++k)
res[k] = a[i];
for (; j < b.size(); ++j, ++k)
res[k] = b[j];
}
static int smart2(const vector<int> &A, vector<vector<int>> &T)
{
int n = A.size();
int res = 0;
int p = int(2e9);
for (int i = 0; i < n; ++i)
T[i+n].assign(1, A[i]);
for (int i = n - 1; i > 0; --i)
merge(T[i], T[i*2], T[i*2+1]);
for (int i = n - 1; i > 0; --i)
{
if (A[i] < p)
{
p = A[i];
int c = 0;
int l = 0 + n;
int r = i + n;
while (l <= r)
{
if (l&1)
c += T[l].size() - (lower_bound(T[l].begin(), T[l].end(), p + 1) - T[l].begin());
if (!(r&1))
c += T[r].size() - (lower_bound(T[r].begin(), T[r].end(), p + 1) - T[r].begin());
l = (l+1)/2;
r = (r-1)/2;
}
res = max(res, c);
}
}
return res;
}
static int smart3(const vector<int> &A, vector<vector<int>> &T)
{
int n = A.size();
int res = 0;
int p = int(2e9);
for (int i = 0; i < n; ++i)
T[i].clear();
for (int i = 0; i < n; ++i)
{
//for (int x = i; x < n; x = (x|(x+1)))
// T[x].push_back(A[i]);
//T[x].insert(lower_bound(T[x].begin(), T[x].end(), A[i]), A[i]);
vector<int> v(1, A[i]);
for (int x = i - 1; x >= 0; x = (x&(x+1))-1)
{
vector<int> v1;
merge(v1, v, T[x]);
swap(v1, v);
}
T[i] = v;
}
for (int i = 0; i < n; ++i)
sort(T[i].begin(), T[i].end());
for (int i = n - 1; i > 0; --i)
{
if (A[i] < p)
{
p = A[i];
int c = 0;
for (int x = i; x >= 0; x = (x&(x+1))-1)
c += T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin());
res = max(res, c);
}
}
return res;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int Q = X.size();
int N = A.size();
vector<int> answer(Q);
vector<vector<int>> T(2*N);
for (int j = 0; j < Q; ++j)
{
A[X[j]] = V[j];
answer[j] = smart3(A, T);
}
return answer;
vector<int> all(N + Q);
for (int i = 0; i < N; ++i)
all[i] = A[i];
for (int i = 0; i < Q; ++i)
all[N+i] = V[i];
sort(all.begin(), all.end());
vector<int>::iterator z = unique(all.begin(), all.end());
all.resize(z - all.begin());
/*for (int j = 0; j < all.size(); ++j)
printf("%d ", all[j]);
printf("\n");*/
if (all.back() <= 100)
{
vector<int> T[101];
for (int x = 0; x <= 100; ++x)
T[x].resize(2*N);
for (int j = 0; j < N; ++j)
for (int x = A[j] - 1; x >= 0; --x)
add(T[x], j, 1);
set<int> pos[101];
for (int j = 0; j < N; ++j)
pos[A[j]].insert(-j);
for (int j = 0; j < Q; j++)
{
int p = X[j];
for (int x = A[p] - 1; x >= 0; --x)
{
add(T[x], p, -1);
}
pos[A[p]].erase(-p);
A[p] = V[j];
for (int x = V[j] - 1; x >= 0; --x)
add(T[x], p, 1);
pos[V[j]].insert(-p);
int ans = 0;
for (int x = 0; x <= 100; ++x)
if (pos[x].size())
{
ans = max(ans, get(T[x], -*(pos[x].begin())));
}
answer[j] = ans;
}
}
else
{
for (int j = 0; j < N; j++)
A[j] = lower_bound(all.begin(), all.end(), A[j]) - all.begin();
for (int j = 0; j < Q; j++)
V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
for (int j = 0; j < Q; j++)
{
A[X[j]] = V[j];
answer[j] = smart(A, F, all);
}
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'void add(std::vector<int>&, int, int)':
bubblesort2.cpp:40:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (; x < f.size(); x |= (x+1))
| ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void merge(std::vector<int>&, const std::vector<int>&, const std::vector<int>&)':
bubblesort2.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (i = 0, j = 0; i < a.size() && j < b.size(); )
| ~~^~~~~~~~~~
bubblesort2.cpp:98:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (i = 0, j = 0; i < a.size() && j < b.size(); )
| ~~^~~~~~~~~~
bubblesort2.cpp:105:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (; i < a.size(); ++i, ++k)
| ~~^~~~~~~~~~
bubblesort2.cpp:107:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (; j < b.size(); ++j, ++k)
| ~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:239:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
239 | for (int j = 0; j < Q; j++)
| ^~~
bubblesort2.cpp:240:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
240 | V[j] = lower_bound(all.begin(), all.end(), V[j]) - all.begin();vector<int> F(all.size());
| ^~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:111:12: warning: 'int smart2(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
111 | static int smart2(const vector<int> &A, vector<vector<int>> &T)
| ^~~~~~
bubblesort2.cpp:73:12: warning: 'int smart1(const std::vector<int>&)' defined but not used [-Wunused-function]
73 | static int smart1(const vector<int> &A)
| ^~~~~~
bubblesort2.cpp:44:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
44 | static int stupid1(vector<int> A)
| ^~~~~~~
bubblesort2.cpp:7:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
7 | static int stupid(vector<int> A)
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1128 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1128 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1098 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1128 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
