Submission #79899

#	Time	Username	Problem	Language	Result	Execution time	Memory
79899		imeimi2000	XOR (IZhO12_xor)	C++17	100 / 100	292 ms	92836 KiB

xor

#include <cstdio>
#include <unordered_map>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n, k;
int ansi, ansk;
int a[250001];

struct node {
    int mx, l, r;
    node() : mx(-1), l(-1), r(-1) {}
} ns[250000 * 31];
int tp = 1;

const int inf = (1 << 30) - 1;
void update(int &i, int s, int e, int x, int v) {
    if (i == -1) i = tp++;
    ns[i].mx = v;
    if (s == e) return;
    int m = (s + e) / 2;
    if (x <= m) update(ns[i].l, s, m, x, v);
    else update(ns[i].r, m + 1, e, x, v);
}

int query(int i, int s, int e, int x) {
    if (i == -1) return -1;
    if (((x ^ s) | (s ^ e)) < k) return -1;
    if (k <= ((x ^ s) & (s ^ e ^ inf))) return ns[i].mx;
    int m = (s + e) / 2;
    return max(query(ns[i].l, s, m, x), query(ns[i].r, m + 1, e, x));
}

int rt = 0;
int main() {
    scanf("%d%d", &n, &k);
    update(rt, 0, inf, 0, 0);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        update(rt, 0, inf, a[i] ^= a[i - 1], i);
    }
    for (int i = 0; i <= n; ++i) {
        int mx = query(rt, 0, inf, a[i]);
        if (ansk < mx - i) ansk = mx - i, ansi = i + 1;
    }
    printf("%d %d\n", ansi, ansk);
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
xor.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100