General

# Author Problem Lang Verdict Time Memory Sent Judged
65727941 Practice:
msuwakow
1261F - 28 GNU C++11 Wrong answer on test 20 1715 ms 251204 KB 2019-11-26 05:01:53 2019-11-26 05:01:53

→ Source
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 30000, M = 16000000, mod = 998244353, inv = (mod + 1) / 2;
const ll inf = (1ll << 60) - 1;

int n, num, ans;
struct node {
ll l, r;
node(ll x = 0, ll y = 0) : l(x), r(y) {}
inline bool operator < (const node &x) const {
if (l != x.l) return l < x.l;
return r > x.r;
}
} seg[M];

struct segmentTree {
//
#define mid ((lt + rt) >> 1)
int root, tot, isEnd[N], ls[N], rs[N];

void insrt(ll x, ll y) {
return insrt(root, x, y, 0, inf);
}

void insrt(int &p, ll x, ll y, ll lt, ll rt) {
if (!p) p = ++tot;assert(tot < N);
if ((lt >= x && rt <= y) || isEnd[p]) {
isEnd[p] = 1;
return;
}
if (x <= mid) insrt(ls[p], x, y, lt, mid);
if (y > mid) insrt(rs[p], x, y, mid + 1, rt);
return;
}

void dfs1(int p, int depA, int depB, ll x, ll lt, ll rt) {
if (!p) return;
if (depA == depB || isEnd[p])
seg[++num] = node(((x ^ lt) | (lt ^ rt)) ^ lt ^ rt, (x ^ lt) | (lt ^ rt));
else
dfs1(ls[p], depA, depB + 1, x, lt, mid), dfs1(rs[p], depA, depB + 1, x, mid + 1, rt);
return;
}

void dfs2(int p, int dep, ll lt, ll rt, segmentTree *tar) {
if (!p) return;
if (isEnd[p])
tar->dfs1(tar->root, dep, 1, lt, 0, inf);
else
dfs2(ls[p], dep + 1, lt, mid, tar), dfs2(rs[p], dep + 1, mid + 1, rt, tar);
return;
}

#undef mid
//
} segA, segB;

template <class T>
x = 0;
char ch = getchar(), w = 0;
while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x = w ? -x : x;
return;
}

inline int calc(ll x, ll y) {
ll a = (y - x + 1) % mod, b = (y + x) % mod;
return a * b % mod * inv % mod;
}

int flag;

int main() {
ll l, r;
while (n--) {
if (l == 191758298353239312) flag = 1;
}
segA.dfs2(segA.root, 1, 0, inf, &segB);assert(num < M);
sort(seg + 1, seg + 1 + num);
ll lst = 0;

if (flag) cout << num << endl;

for (R int i = 1; i <= num; ++i) {
if (seg[i].r <= lst) continue;
ans = (ans + calc(seg[i].l, seg[i].r)) % mod, lst = seg[i].r;
}
cout << ans << endl;
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
Checker comment
?
Diagnostics
?
Click to see test details