oj.uz

답안 #79899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79899 2018-10-17T05:59:16 Z imeimi2000 XOR (IZhO12_xor) C++17
100 / 100
 292 ms 92836 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 91384 KB Output is correct
2 Correct 80 ms 91640 KB Output is correct
3 Correct 77 ms 91640 KB Output is correct
4 Correct 77 ms 91640 KB Output is correct
5 Correct 88 ms 91804 KB Output is correct
6 Correct 90 ms 91804 KB Output is correct
7 Correct 96 ms 91804 KB Output is correct
8 Correct 115 ms 91804 KB Output is correct
9 Correct 174 ms 92156 KB Output is correct
10 Correct 139 ms 92284 KB Output is correct
11 Correct 137 ms 92284 KB Output is correct
12 Correct 140 ms 92284 KB Output is correct
13 Correct 143 ms 92284 KB Output is correct
14 Correct 141 ms 92284 KB Output is correct
15 Correct 134 ms 92284 KB Output is correct
16 Correct 138 ms 92284 KB Output is correct
17 Correct 266 ms 92680 KB Output is correct
18 Correct 292 ms 92836 KB Output is correct
19 Correct 262 ms 92836 KB Output is correct
20 Correct 269 ms 92836 KB Output is correct