fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  5.  
  6. #define ll long long
  7. #define ull unsigned long long
  8. #define ld long double
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define mp make_pair
  12. #define fi first
  13. #define se second
  14.  
  15. #define sz(v) ((int)(v).size())
  16. #define all(v) (v).begin(), (v).end()
  17. #define rall(v) (v).rbegin(), (v).rend()
  18. #define clr(v, d) memset(v, d, sizeof(v))
  19.  
  20. #define forn(i, e) for (int i = 0; i < e; i++)
  21. #define fors(i, s, e) for (int i = s; i < e; i++)
  22. #define rforn(i, s) for (int i = s; i >= 0; i--)
  23. #define rfors(i, s, e) for (int i = s; i >= e; i--)
  24.  
  25. #define msb(x) (63 - __builtin_clzll((long long)(x)))
  26. #define lsb(x) (__builtin_ctzll((unsigned long long)(x)))
  27. #define bit_count(x) (__builtin_popcountll((unsigned long long)(x)))
  28.  
  29. #ifndef ONLINE_JUDGE
  30. #define debug(x) cerr << #x << " = " << (x) << '\n';
  31. #else
  32. #define debug(x)
  33. #endif
  34.  
  35. typedef vector<int>       vi;
  36. typedef vector<double>    vd;
  37. typedef vector< vi >      vvi;
  38. typedef vector< vd >      vvd;
  39. typedef vector<string>    vs;
  40.  
  41. const int INF = 1e9 + 7;
  42. const ll LINF = 1e18 + 7;
  43. const double EPS = 1e-9;
  44. const int MAXN = 1e6 + 5;
  45. const int LOG = 20;
  46. // #define int ll
  47.  
  48. const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
  49. const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
  50.  
  51. struct BinaryTrie {
  52.     struct Node {
  53.         int ch[2] {-1,-1};
  54.         int mn = INT_MAX;
  55.     };
  56.  
  57.     vector<Node> trie;
  58.  
  59.     BinaryTrie() {trie.emplace_back();}
  60.  
  61.     void insert(int val,int i) {
  62.         int u = 0;
  63.         trie[u].mn = min(trie[u].mn, i);
  64.         for (int b = 29;b >= 0; b--) {
  65.             int bit = (val >> b) & 1;
  66.             if (trie[u].ch[bit] == -1) {
  67.                 trie[u].ch[bit] = sz(trie);
  68.                 trie.emplace_back();
  69.             }
  70.             u = trie[u].ch[bit];
  71.             trie[u].mn = min(trie[u].mn, i);
  72.         }
  73.     }
  74.  
  75.     int earliestAtLeast(int val,int x) {
  76.         int u = 0,ans = INT_MAX;
  77.         for (int b = 29;b >= 0 && u != -1; b--) {
  78.             int bv = (val >> b) & 1;
  79.             int bx = (x >> b) & 1;
  80.  
  81.             if (bx == 1) {
  82.                 u = trie[u].ch[bv ^ 1];
  83.             }else {
  84.                 int greater = trie[u].ch[bv ^ 1];
  85.                 if (greater != -1) {
  86.                     ans = min(ans,trie[greater].mn);
  87.                 }
  88.                 u = trie[u].ch[bv];
  89.             }
  90.         }
  91.         if (u != -1) {
  92.             ans = min(ans,trie[u].mn);
  93.         }
  94.         return ans;
  95.     }
  96. };
  97.  
  98. void solve() {
  99.     int n,x; cin >> n >> x;
  100.  
  101.     BinaryTrie tr;
  102.     tr.insert(0,0);
  103.  
  104.     int pref = 0,best_len = 0,best_start = 1;
  105.     for (int r = 1;r <= n;r++) {
  106.         int a;
  107.         cin >> a;
  108.         pref ^= a;
  109.  
  110.         int j = tr.earliestAtLeast(pref,x);
  111.         if (j != INT_MAX) {
  112.             int s = j + 1;
  113.             int len = r - j;
  114.  
  115.             if (len > best_len || (len == best_len && s < best_start)) {
  116.                 best_len = len;
  117.                 best_start = s;
  118.             }
  119.             tr.insert(pref,r);
  120.         }
  121.     }
  122.  
  123.     cout << best_start << " " << best_len << endl;
  124. }
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131. signed main() {
  132. #ifndef ONLINE_JUDGE
  133.     freopen("c.in", "r", stdin);
  134.     freopen("c.out", "w", stdout);
  135. #endif
  136.  
  137.     FastIO
  138.     int tc = 1;
  139.     // cin >> tc;
  140.  
  141.  
  142.     while (tc--) {
  143.         solve();
  144.     }
  145.  
  146.  
  147.     return 0;
  148. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 0
https://ideone.com/RBeS9O
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!