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>
inline void read(T &x) {
    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;
    read(n);
    while (n--) {
        read(l), read(r), segA.insrt(l, r);
        if (l == 191758298353239312) flag = 1;
    }
    read(n);
    while (n--) read(l), read(r), segB.insrt(l, r);
    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
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details