oj.uz

답안 #339459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339459 2020-12-25T10:42:23 Z Vladikus004 XOR (IZhO12_xor) C++14
100 / 100
 299 ms 51820 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

struct node{
    int mx;
    node *nxt[2];
    node(){
        mx = -1;
        nxt[0]=nxt[1]=nullptr;
    }
};

node *root = new node();
const int N = 250000 + 3;
int n, x, a[N];

void add(node *cur, int x, int h, int pos){
    if (h == 0) {
        cur->mx = max(cur->mx, pos);
        return;
    }
    int bt = (x>>h)&1;
    if (!cur->nxt[bt]) cur->nxt[bt] = new node();
    add(cur->nxt[bt], x, h-1, pos);
    if (cur->nxt[0]) cur->mx = max(cur->mx, cur->nxt[0]->mx);
    if (cur->nxt[1]) cur->mx = max(cur->mx, cur->nxt[1]->mx);
}

int get_mx(node *cur, int xr, int h, int is){
    if (h == 0 || is) return cur->mx;
    int bt = (x>>h)&1, xrbt = (xr>>h)&1;
    int ans = -1;
    if (cur->nxt[1^xrbt]){
        if (bt) ans = max(ans, get_mx(cur->nxt[1^xrbt], xr, h-1, 0));
        else ans = max(ans, get_mx(cur->nxt[1^xrbt], xr, h-1, 1));
    }
    if (cur->nxt[xrbt]){
        if (!bt) ans = max(ans, get_mx(cur->nxt[xrbt], xr, h-1, 0));
    }
    return ans;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> a[i];
    pii mx = {-1, -1};
    int xr = 0;
    add(root, 0, 31, n);
    for (int i = n - 1; i >= 0; i--){
        xr ^= a[i];
        add(root, xr, 31, i);
        mx = max(mx, mp(get_mx(root, xr, 31, 0) - i, -i));
    }
    cout << (-mx.ss) + 1 << " " << mx.ff;
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 13 ms 1388 KB Output is correct
6 Correct 17 ms 1516 KB Output is correct
7 Correct 17 ms 1516 KB Output is correct
8 Correct 19 ms 1644 KB Output is correct
9 Correct 108 ms 24812 KB Output is correct
10 Correct 116 ms 24940 KB Output is correct
11 Correct 108 ms 24812 KB Output is correct
12 Correct 112 ms 24940 KB Output is correct
13 Correct 110 ms 24940 KB Output is correct
14 Correct 109 ms 24940 KB Output is correct
15 Correct 109 ms 24940 KB Output is correct
16 Correct 110 ms 24940 KB Output is correct
17 Correct 289 ms 51692 KB Output is correct
18 Correct 299 ms 51820 KB Output is correct
19 Correct 298 ms 51724 KB Output is correct
20 Correct 286 ms 51692 KB Output is correct