Submission #38921

#	Time	Username	Problem	Language	Result	Execution time	Memory
38921		Talant	XOR (IZhO12_xor)	C++14	0 / 100	0 ms	16076 KiB

xor

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e18 + 7;
const ll N = (ll)3e5 + 7;

ll n,x;
ll a[N],p[N];
ll t[N * 4];
ll id,k = -1;

void build (ll v = 1,ll tl = 1,ll tr = n) {
        if (tl == tr)
                t[v] = p[tl];
        else {
                ll tm = (tl + tr) >> 1;

                build (v + v,tl,tm);
                build (v + v + 1,tm + 1,tr);

                t[v] = max(t[v + v],t[v + v + 1]);
        }
}
ll get (ll l,ll r,ll v = 1,ll tl = 1,ll tr = n) {
        if (tl > r || tr < l)
                return -inf;
        if (l <= tl && tr <= r)
                return t[v];

        ll tm = (tl + tr) >> 1;

        return max(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
int main () {
        scanf ("%lld%lld", &n,&x);

        for (ll i = 1; i <= n; i ++) {
                scanf ("%lld", &a[i]);
                p[i] = (p[i - 1] ^ a[i]);
        }

        build ();

        for (ll i = 1; i <= n; i ++){
                ll l = i,r = n;
                ll cur = (p[i - 1] ^ x);

                while (r - l > 1) {
                        ll m = (r + l) >> 1;
                        if (get(m,n) >= cur)
                                l = m;
                        else
                                r = m;
                }
                if (get(r,n) >= cur)
                        l = r;
                ll o = 0;
                if (get(l,n) < cur)
                        o = 0;
                else
                        o = l - i + 1;
                if (k < o)
                        id = i,k = o;
        }
        cout << id << " " << k << endl;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:44:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%lld%lld", &n,&x);
                                  ^
xor.cpp:47:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%lld", &a[i]);
                                      ^

• Subtask 1: 0 / 100