#include <bits/stdc++.h>
using namespace std;
class Set {
private:
#define sub(p) (p == NULL ? 0 : p->nr)
#define hight(p) (p == NULL ? 0 : p->hight)
#define getBalanced(p) (p == NULL ? 0 : hight(p->left) - hight(p->right))
struct nod {
int val, hight, nr, fr;
nod* left, * right;
};
nod* root;
inline nod* New(int val)
{
nod* p = new nod;
p->val = val;
p->left = p->right = NULL;
p->nr = p->hight = 1;
p->fr = 1;
return p;
}
inline nod* to_right(nod* x)
{
nod* y = x->left;
nod* z = y->right;
y->right = x;
x->left = z;
x->hight = max(hight(x->left), hight(x->right)) + 1;
y->hight = max(hight(y->left), hight(y->right)) + 1;
x->nr = sub(x->left) + sub(x->right) + x->fr;
y->nr = sub(y->left) + sub(y->right) + y->fr;
return y;
}
inline nod* to_left(nod* x)
{
nod* y = x->right;
nod* z = y->left;
y->left = x;
x->right = z;
x->hight = max(hight(x->left), hight(x->right)) + 1;
y->hight = max(hight(y->left), hight(y->right)) + 1;
x->nr = sub(x->left) + sub(x->right) + x->fr;
y->nr = sub(y->left) + sub(y->right) + y->fr;
return y;
}
nod* add(nod* root, int val)
{
if (root == NULL)
return New(val);
if (root->val < val)
root->right = add(root->right, val);
else if (root->val > val)
root->left = add(root->left, val);
else
{
root->fr++;
root->nr++;
return root;
}
root->hight = max(hight(root->left), hight(root->right)) + 1;
root->nr = sub(root->left) + sub(root->right) + root->fr;
int b = getBalanced(root);
if (b > 1)
{
if (val < root->left->val)
return to_right(root);
else
{
root->left = to_left(root->left);
return to_right(root);
}
}
else if (b < -1)
{
if (val > root->right->val)
return to_left(root);
else
{
root->right = to_right(root->right);
return to_left(root);
}
}
return root;
}
int greaterThan(nod* p, int& val)
{
if (p == NULL)
return 0;
if (p->val < val)
return greaterThan(p->right, val);
return p->fr + greaterThan(p->left, val) + sub(p->right);
}
int lessThanPrv(nod* p, int& val)
{
if (p == NULL)
return 0;
if (p->val > val)
return lessThanPrv(p->left, val);
return p->fr + lessThanPrv(p->right, val) + sub(p->left);
}
int intervalPrv(nod* p, int& l, int& r)
{
if (p == NULL)
return 0;
if (p->val < l)
return intervalPrv(p->right, l, r);
else if (r < p->val)
return intervalPrv(p->left, l, r);
return p->fr + greaterThan(p->left, l) + lessThanPrv(p->right, r);
}
public:
Set()
{
root = NULL;
}
void clear()
{
root = NULL;
}
void insert(int val)
{
if (root == NULL)
{
root = new nod;
root->nr = root->hight = 1;
root->left = root->right = NULL;
root->val = val;
root->fr = 1;
return;
}
root = add(root, val);
}
int interval(int l, int r)
{
if (l > r)
return 0;
return intervalPrv(root, l, r);
}
int lessThan(int val)
{
return lessThanPrv(root, val);
}
int greaterThan(int val)
{
return greaterThan(root, val);
}
};
// (((1 << k) <= nr && nr < (1 << (k + 1))) || (nr >= (1 << k) + (1 << (k + 1))))
int v[1000001], x[1000001], n;
int* vp, * xp;
long long bit[30];
Set S;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i];
return 0;
for (int k = 0; k <= 29; k++)
{
vp = v;
vp++;
xp = x;
xp++;
for (int i = 1; i <= n; i++)
{
if (*vp & 1)
*xp += (1 << k);
*vp >>= 1;
S.insert(*xp);
bit[k] += S.interval((1 << k) - *xp, (1 << (k + 1)) - *xp - 1) + S.greaterThan((1 << k) + (1 << (k + 1)) - *xp);
vp++;
xp++;
}
S.clear();
}
int res = 0;
for (int k = 0; k <= 29; k++)
if (bit[k] & 1)
res += (1 << k);
cout << res;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
216 ms |
4076 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
216 ms |
4076 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |