Submission #261599

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261599	2020-08-11T22:02:17 Z	sckmd	XOR (IZhO12_xor)	C++14	100 / 100	260 ms	59512 KB

xor

    #include <bits/stdc++.h>
     
    using namespace std;
    #define MAXN 500005
    int a[MAXN];
     
    struct node
    {
      node* nula;
      node* kec;
      int minpos=9999999;
      //bool leaf;
    };
    node* root;
     
    void update(int br,int pos)
    {
      node* now = root;
      for(int i = 31; i >= 0; i--)
      {
        //if(now->minpos == NULL)now->minpos = 999999999;
        now->minpos = min(now->minpos,pos);
        if(br&(1<<i))
        {
          if(now->kec == NULL)now->kec = new node();
          now = now->kec;
        }
        else
        {
          if(now->nula == NULL)now->nula = new node();
          now = now->nula;
        }
      }
      //if(now->minpos == NULL)now->minpos = 999999999;
      now->minpos = min(now->minpos,pos);
    }
    int query(int br,int x)
    {
      //br je trazeni
      //x je mojbroj
      node* now = root;
      int res = 9999999;
      int i;
      for(i = 31; i >= 0; i--)
      {
        if(br & (1<<i))
        {
          if(x & (1<<i))
          {
            if(now->nula == NULL)break;
            now = now->nula;
          }
          else
          {
            if(now->kec == NULL)break;
            now = now->kec;
          }
        }
        else
        {
          if(x & (1<<i))
          {
            if(now->nula != NULL)res = min(res,now->nula->minpos);
            if(now->kec == NULL)break;
            now = now->kec;
          }
          else
          {
            if(now->kec != NULL)res = min(res,now->kec->minpos);
            if(now->nula == NULL)break;
            now = now->nula;
          }
        }
      }
      if(i==-1)res = min(res,now->minpos);
      return res;
    }
     
    int main()
    {
      ios_base::sync_with_stdio(false);
      int n,x;
      cin >> n >> x;
      root = new node();
      update(0,1);
      for(int i = 1; i <= n; i++)
      {
        cin >> a[i];
        a[i]^=a[i-1];
      }
      int ans = 0;
      int j = 0;
      for(int i = 1; i <= n; i++)
      {
      	int tr = i-query(x,a[i]);
      	if(tr > ans)ans=tr,j=i;
        update(a[i],i);
      }
      cout << j-ans+1 << " " << ans;
      return 0;
    }

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	640 KB	Output is correct
5	Correct	9 ms	1920 KB	Output is correct
6	Correct	11 ms	2176 KB	Output is correct
7	Correct	12 ms	2176 KB	Output is correct
8	Correct	12 ms	2304 KB	Output is correct
9	Correct	91 ms	27912 KB	Output is correct
10	Correct	89 ms	28152 KB	Output is correct
11	Correct	93 ms	27896 KB	Output is correct
12	Correct	94 ms	28024 KB	Output is correct
13	Correct	98 ms	28024 KB	Output is correct
14	Correct	94 ms	28152 KB	Output is correct
15	Correct	99 ms	28024 KB	Output is correct
16	Correct	103 ms	28024 KB	Output is correct
17	Correct	260 ms	59388 KB	Output is correct
18	Correct	242 ms	59512 KB	Output is correct
19	Correct	242 ms	59512 KB	Output is correct
20	Correct	259 ms	59384 KB	Output is correct