#include "bubblesort2.h"
#include <cstdio>
#include <string>
#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)
printf("%d ", A[i]);
printf("\n");*/
vector<int> v, v1;
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]);
v.assign(1, A[i]);
v1.clear();
int y = (i&(i+1))-1;
for (int x = i - 1; x > y; x = (x&(x+1))-1)
{
merge(v1, v, T[x]);
swap(v1, v);
}
T[i] = v;
}
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;
}
struct node
{
node *left;
node *right;
int h;
int v;
int v1;
int sz;
int pv;
int mv;
};
void traverse(node *a)
{
if (!a)
return;
traverse(a->left);
printf("%d ", a->v);
fflush(stdout);
traverse(a->right);
}
string tostr(node *a)
{
if (!a)
return string();
string r = tostr(a->left);
char tmp[20];
sprintf(tmp," (%d, %d, %d)", a->v, a->v1, a->mv);
r += tmp;
return r + tostr(a->right);
}
node * merge(node *a, node *b)
{
if (!a)
return b;
if (!b)
return a;
node *r = new node();
if (a->h < b->h)
{
*r = *a;
node *a_right = a->right;
if (r->pv)
{
int delta = r->pv;
if (a->left)
{
node *nl = new node();
*nl = *a->left;
nl->pv += delta;
nl->mv += delta;
nl->v1 += delta;
r->left = nl;
}
if (a->right)
{
a_right = new node();
*a_right = *a->right;
a_right->pv += delta;
a_right->mv += delta;
a_right->v1 += delta;
}
r->pv = 0;
}
r->right = merge(a_right, b);
}
else
{
*r = *b;
node *b_left = b->left;
if (r->pv)
{
int delta = r->pv;
if (b->right)
{
node *nr = new node();
*nr = *b->right;
nr->pv += delta;
nr->mv += delta;
nr->v1 += delta;
r->right = nr;
}
if (b->left)
{
b_left = new node();
*b_left = *b->left;
b_left->pv += delta;
b_left->mv += delta;
b_left->v1 += delta;
}
r->pv = 0;
}
r->left = merge(a, b_left);
}
r->sz = 1;
r->mv = r->v1;
if (r->left)
{
r->sz += r->left->sz;
r->mv = max(r->mv, r->left->mv);
}
if (r->right)
{
r->sz += r->right->sz;
r->mv = max(r->mv, r->right->mv);
}
return r;
}
pair<node*,node*> split(node *a, int x)
{
if (!a)
return pair<node*,node*>((node*)0, (node*)0);
pair<node*,node*> tmp;
if (x <= a->v)
{
tmp = split(a->left,x);
node * z = new node();
*z = *a;
z->left = NULL;
if (a->left)
z->sz -= a->left->sz;
z->mv = z->v1;
if (z->right)
z->mv = max(z->mv, z->right->mv + z->pv);
return pair<node*,node*>(tmp.first, merge(tmp.second,z));
}
else
{
tmp = split(a->right,x);
node * z = new node();
*z = *a;
z->right = NULL;
if (a->right)
z->sz -= a->right->sz;
z->mv = z->v1;
if (z->left)
z->mv = max(z->mv, z->left->mv + z->pv);
return pair<node*,node*>(merge(z, tmp.first), tmp.second);
}
}
node * removefirst(node *a)
{
//string z = tostr(a);
node *r = NULL;
//string ll = tostr(a->left);
//string rr = tostr(a->right);
if (a->left)
{
node *q = new node();
*q = *a;
q->left = NULL;
q->sz -= a->left->sz;
r = merge(removefirst(a->left), q);
}
else
r = a->right;
//printf("remove first (%s) (%s) (%s) = %s\n", z.c_str(), ll.c_str(), rr.c_str(), tostr(r).c_str());
return r;
}
int getsz(node *a, int x)
{
if (!a)
return 0;
if (a->v < x)
return (a->left ? a->left->sz : 0) + 1 + getsz(a->right, x);
return getsz(a->left, x);
}
static int smart4(const vector<int> &A)
{
int n = A.size();
int res = 0;
int p = int(2e9);
vector<node*> D(2*n);
{
vector<vector<int>> T(2*n);
/*for (int i = 0; i < n; ++i)
printf("%d ", A[i]);
printf("\n");*/
vector<int> v, v1;
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]);
v.assign(1, A[i]);
v1.clear();
int y = (i&(i+1))-1;
for (int x = i - 1; x > y; x = (x&(x+1))-1)
{
merge(v1, v, T[x]);
swap(v1, v);
}
T[i] = v;
D[i] = NULL;
for (int j = 0; j < v.size(); ++j)
{
node *nd = new node();
nd->h = rand()*32000+rand();
nd->v = v[j];
nd->left = NULL;
nd->right = NULL;
nd->sz = 1;
D[i] = merge(D[i], nd);
}
}
}
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)
{
//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
c += D[x]->sz - getsz(D[x], p+1);
}
res = max(res, c);
}
}
return res;
}
static int smart5(const vector<int> &A, vector<node*> &D)
{
int n = A.size();
int res = 0;
int p = int(2e9);
if (D.size() == 0)
{
D.resize(2*n);
vector<vector<int>> T(2*n);
/*for (int i = 0; i < n; ++i)
printf("%d ", A[i]);
printf("\n");*/
vector<int> v, v1;
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]);
v.assign(1, A[i]);
v1.clear();
int y = (i&(i+1))-1;
for (int x = i - 1; x > y; x = (x&(x+1))-1)
{
merge(v1, v, T[x]);
swap(v1, v);
}
T[i] = v;
D[i] = NULL;
for (int j = 0; j < v.size(); ++j)
{
node *nd = new node();
nd->h = rand()*32000+rand();
nd->v = v[j];
nd->left = NULL;
nd->right = NULL;
nd->sz = 1;
D[i] = merge(D[i], nd);
}
}
}
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)
{
//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
c += D[x]->sz - getsz(D[x], p+1);
}
res = max(res, c);
}
}
return res;
}
vector<int> countScans1(vector<int> A, vector<int> X, vector<int> V)
{
int Q = X.size();
int N = A.size();
vector<int> answer(Q);
vector<node*> D;
//vector<vector<int>> T(N);
for (int j = 0; j < Q; ++j)
{
//printf("j %d\n", j);
if (j != 0)
{
//for (int x = 0; x < N; ++x)
// printf("%d ", A[x]);
//printf("\n");
//printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);
for (int x = X[j]; x < N; x = (x|(x+1)))
{
//printf("D[%d] = %d (sz = %d)\n", x, D[x], D[x]->sz);
//traverse(D[x]);
//printf("\n");
pair<node*,node*> tmp = split(D[x], A[X[j]]);
//traverse(tmp.first);
//printf(", ");
//traverse(tmp.second);
//printf("\n");
tmp.second = removefirst(tmp.second);
//traverse(tmp.second);
//printf("\n");
node * q = merge(tmp.first, tmp.second);
//printf("=");
//traverse(q);
//printf("\n");
tmp = split(q,V[j]);
node * nn = new node();
nn->h = rand()*32000+rand();
nn->left = 0;
nn->right = 0;
nn->sz = 1;
nn->v = V[j];
//printf("D[%d] = ", x);
D[x] = merge(merge(tmp.first, nn), tmp.second);
//traverse(D[x]);
//printf("\n");
}
}
A[X[j]] = V[j];
answer[j] = smart5(A, D);
}
return answer;
}
node* getleft(node *a)
{
if (a->left)
return getleft(a->left);
return a;
}
vector<node*> DS;
vector<vector<pair<int,int>>> DP;
void apply_push(int x)
{
vector<pair<int,int>> &v = DP[x];
for (int i = 0; i < v.size(); ++i)
{
int a = v[i].first;
int delta = v[i].second;
if (x*2+1 < DP.size())
{
DP[x*2].push_back(v[i]);
DP[x*2+1].push_back(v[i]);
}
pair<node*,node*> q = split(DS[x], a);
//printf("after split \"%s\" \"%s\"\n", tostr(q.first).c_str(), tostr(q.second).c_str());
if (q.first)
{
node *nn = new node();
*nn = *(q.first);
nn->pv += delta;
nn->mv += delta;
nn->v1 += delta;
DS[x] = merge(nn, q.second);
}
else
DS[x] = q.second;
}
v.clear();
}
void merge_seq(int x)
{
apply_push(x*2+1);
node *right = DS[x*2+1];
int cut;
if (right)
cut = getleft(right)->v;
else
cut = int(2e9);
apply_push(x*2);
node *left = DS[x*2];
pair<node*, node*> tmp = split(left, cut);
DS[x] = merge(tmp.first, right);
}
void add_ab(int x, int a, int v)
{
DP[x].push_back(pair<int,int>(a,v));
}
void dsupdate(int x, int pos, int was, int now, int inv, int L, int R)
{
//printf("%d %d %d\n", x, L, R);
if (R < pos)
return;
if (pos < L)
{
add_ab(x, was, -1);
add_ab(x, now, 1);
return;
}
if (L == R)
{
DP[x].clear();
node * nn = new node();
*nn = *(DS[x]);
nn->v = now;
nn->v1 = inv;
nn->pv = 0;
nn->mv = inv;
DS[x] = nn;
return;
}
int z = DP[x].size();
for (int i = 0; i < z; ++i)
{
DP[2*x].push_back(DP[x][i]);
DP[2*x+1].push_back(DP[x][i]);
}
DP[x].clear();
int m = (L + R)/2;
dsupdate(2 * x, pos, was, now, inv, L, m);
dsupdate(2 * x + 1, pos, was, now, inv, m + 1, R);
merge_seq(x);
//printf("DS[%d]=%s\n",x,tostr(DS[x]).c_str());
}
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<node*> D(N);
int TSTART = 2;
while (TSTART / 2 < N)
TSTART *= 2;
DS.resize(2*TSTART);
DP.resize(2*TSTART);
for (int j = 0; j < Q; ++j)
{
//printf("j %d\n", j);
if (j == 0)
{
vector<vector<int>> T(2*N);
A[X[j]] = V[j];
/*for (int i = 0; i < N; ++i)
printf("%d ", A[i]);
printf("\n");*/
vector<int> v, v1;
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]);
v.assign(1, A[i]);
v1.clear();
int y = (i&(i+1))-1;
for (int x = i - 1; x > y; x = (x&(x+1))-1)
{
merge(v1, v, T[x]);
swap(v1, v);
}
T[i] = v;
D[i] = NULL;
for (int j = 0; j < v.size(); ++j)
{
node *nd = new node();
nd->h = rand()*32000+rand();
nd->v = v[j];
nd->left = NULL;
nd->right = NULL;
nd->sz = 1;
D[i] = merge(D[i], nd);
}
}
for (int i = 0; i < N; ++i)
{
int p = A[i];
int c = 0;
for (int x = i; x >= 0; x = (x&(x+1))-1)
{
//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
c += D[x]->sz - getsz(D[x], p+1);
}
node *nd = new node();
nd->h = rand()*32000+rand();
nd->v = A[i];
nd->v1 = c;
nd->pv = 0;
nd->mv = c;
nd->sz = 1;
DS[i+TSTART] = nd;
}
for (int i = TSTART-1; i > 0; --i)
{
//printf("merge_seq(%d) =", i);
merge_seq(i);
//printf("%s\n", tostr(DS[i]).c_str());
}
}
else
{
/*for (int x = 0; x < N; ++x)
printf("%d ", A[x]);
printf("\n");
printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);*/
int awas = A[X[j]];
for (int x = X[j]; x < N; x = (x|(x+1)))
{
//printf("D[%d] = %d (sz = %d)\n", x, D[x], D[x]->sz);
//traverse(D[x]);
//printf("\n");
pair<node*,node*> tmp = split(D[x], awas);
//traverse(tmp.first);
//printf(", ");
//traverse(tmp.second);
//printf("\n");
tmp.second = removefirst(tmp.second);
//traverse(tmp.second);
//printf("\n");
node * q = merge(tmp.first, tmp.second);
//printf("=");
//traverse(q);
//printf("\n");
tmp = split(q,V[j]);
node * nn = new node();
nn->h = rand()*32000+rand();
nn->left = 0;
nn->right = 0;
nn->sz = 1;
nn->v = V[j];
//printf("D[%d] = ", x);
D[x] = merge(merge(tmp.first, nn), tmp.second);
//traverse(D[x]);
//printf("\n");
}
{
int p = V[j];
int c = 0;
for (int x = X[j]; x >= 0; x = (x&(x+1))-1)
{
//printf("yo %d %s\n", x, tostr(D[x]).c_str());
//printf("%d %d\n",T[x].size() - (lower_bound(T[x].begin(), T[x].end(), p + 1) - T[x].begin()),D[x]->sz - getsz(D[x], p+1));
c += D[x]->sz - getsz(D[x], p+1);
}
//printf("dsupdate inv = %d\n", c);
dsupdate(1, X[j], awas, V[j], c, 0, TSTART-1);
}
/*{
int x = TSTART + X[j];
node * nn = new node();
*nn = *(DS[x]);
nn->v = V[j];
nn->mv = v;
while( x > 1 )
{
x /= 2;
merge_seq(x);
}
}*/
}
A[X[j]] = V[j];
apply_push(1);
//printf("ans=%d\n", DS[1]->mv);
answer[j] = DS[1]->mv;//smart5(A, D);
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'void add(std::vector<int>&, int, int)':
bubblesort2.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | 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:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (i = 0, j = 0; i < a.size() && j < b.size(); )
| ~~^~~~~~~~~~
bubblesort2.cpp:100:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (i = 0, j = 0; i < a.size() && j < b.size(); )
| ~~^~~~~~~~~~
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 (; i < a.size(); ++i, ++k)
| ~~^~~~~~~~~~
bubblesort2.cpp:109:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (; j < b.size(); ++j, ++k)
| ~~^~~~~~~~~~
bubblesort2.cpp: In function 'int smart4(const std::vector<int>&)':
bubblesort2.cpp:385:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
385 | for (int j = 0; j < v.size(); ++j)
| ~~^~~~~~~~~~
bubblesort2.cpp: In function 'int smart5(const std::vector<int>&, std::vector<node*>&)':
bubblesort2.cpp:442:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
442 | for (int j = 0; j < v.size(); ++j)
| ~~^~~~~~~~~~
bubblesort2.cpp: In function 'void apply_push(int)':
bubblesort2.cpp:536:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
536 | for (int i = 0; i < v.size(); ++i)
| ~~^~~~~~~~~~
bubblesort2.cpp:540:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
540 | if (x*2+1 < DP.size())
| ~~~~~~^~~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:657:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
657 | for (int j = 0; j < v.size(); ++j)
| ~~^~~~~~~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:358:12: warning: 'int smart4(const std::vector<int>&)' defined but not used [-Wunused-function]
358 | static int smart4(const vector<int> &A)
| ^~~~~~
bubblesort2.cpp:145:12: warning: 'int smart3(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
145 | static int smart3(const vector<int> &A, vector<vector<int>> &T)
| ^~~~~~
bubblesort2.cpp:113:12: warning: 'int smart2(const std::vector<int>&, std::vector<std::vector<int> >&)' defined but not used [-Wunused-function]
113 | static int smart2(const vector<int> &A, vector<vector<int>> &T)
| ^~~~~~
bubblesort2.cpp:75:12: warning: 'int smart1(const std::vector<int>&)' defined but not used [-Wunused-function]
75 | static int smart1(const vector<int> &A)
| ^~~~~~
bubblesort2.cpp:61:12: warning: 'int smart(const std::vector<int>&, std::vector<int>&, const std::vector<int>&)' defined but not used [-Wunused-function]
61 | static int smart(const vector<int> &A, vector<int> &F, const vector<int> &all)
| ^~~~~
bubblesort2.cpp:46:12: warning: 'int stupid1(std::vector<int>)' defined but not used [-Wunused-function]
46 | static int stupid1(vector<int> A)
| ^~~~~~~
bubblesort2.cpp:9:12: warning: 'int stupid(std::vector<int>)' defined but not used [-Wunused-function]
9 | static int stupid(vector<int> A)
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
39916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
39916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
706 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
39916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
