fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Problem: Array of n bits (0 or 1), initially unknown
  5. // Given m queries: XOR of bits in range [l, r] equals v
  6. // Check if queries are consistent (valid assignment exists)
  7.  
  8. // DSU with parity/XOR tracking between nodes
  9. struct ParityDSU {
  10.     vector<int> p;    // parent
  11.     vector<int> rk;   // rank for union by rank
  12.     vector<int> xr;   // XOR relationship to parent
  13.  
  14.     ParityDSU(int sz = 0) {
  15.         init(sz);
  16.     }
  17.  
  18.     void init(int sz) {
  19.         p.resize(sz);
  20.         rk.assign(sz, 0);
  21.         xr.assign(sz, 0);
  22.         iota(p.begin(), p.end(), 0);
  23.     }
  24.  
  25.     // Returns {root, xor_value_from_u_to_root}
  26.     // Maintains invariant: value[u] XOR xr[u] = value[parent[u]]
  27.     pair<int, int> find(int u) {
  28.         if (p[u] == u) {
  29.             return {u, 0};
  30.         }
  31.  
  32.         // Path compression: update XOR value along path
  33.         auto [rt, x] = find(p[u]);
  34.         xr[u] ^= x;  // Update XOR to root
  35.         p[u] = rt;
  36.  
  37.         return {p[u], xr[u]};
  38.     }
  39.  
  40.     // Add constraint: value[a] XOR value[b] = val
  41.     bool add(int a, int b, int val) {
  42.         auto [ra, xa] = find(a);  // xa = value[a] XOR value[ra]
  43.         auto [rb, xb] = find(b);  // xb = value[b] XOR value[rb]
  44.  
  45.         // Already in same component - check consistency
  46.         if (ra == rb) {
  47.             // value[a] XOR value[b] = (value[a] XOR value[ra]) XOR (value[ra] XOR value[b])
  48.             //                       = xa XOR xb
  49.             return (xa ^ xb) == val;
  50.         }
  51.  
  52.         // Merge two components with union by rank
  53.         if (rk[ra] < rk[rb]) {
  54.             swap(ra, rb);
  55.             swap(xa, xb);
  56.         }
  57.  
  58.         // Make rb point to ra
  59.         p[rb] = ra;
  60.         // value[rb] XOR xr[rb] should equal value[ra]
  61.         // We know: value[a] = value[ra] XOR xa, value[b] = value[rb] XOR xb
  62.         // Given: value[a] XOR value[b] = val
  63.         // So: (value[ra] XOR xa) XOR (value[rb] XOR xb) = val
  64.         // Therefore: value[rb] XOR value[ra] = xa XOR xb XOR val
  65.         xr[rb] = xa ^ xb ^ val;
  66.  
  67.         if (rk[ra] == rk[rb]) {
  68.             rk[ra]++;
  69.         }
  70.  
  71.         return true;
  72.     }
  73. };
  74.  
  75. class Solution {
  76. public:
  77.     // Check if parity queries are consistent
  78.     bool check(long long n, vector<array<long long, 3>>& qs) {
  79.         // Key idea: XOR of range [l, r] = prefix[r+1] XOR prefix[l]
  80.         // where prefix[i] = XOR of bits [0, i-1]
  81.         // So query [l, r] = v means: prefix[l] XOR prefix[r+1] = v
  82.  
  83.         // Collect all relevant prefix positions
  84.         vector<long long> pts;
  85.         pts.push_back(0);  // Always include prefix[0]
  86.  
  87.         for (auto& q : qs) {
  88.             pts.push_back(q[0]);      // left endpoint
  89.             pts.push_back(q[1] + 1);  // right endpoint + 1
  90.         }
  91.  
  92.         // Coordinate compression (positions can be up to 10^9)
  93.         sort(pts.begin(), pts.end());
  94.         pts.erase(unique(pts.begin(), pts.end()), pts.end());
  95.  
  96.         auto get = [&](long long v) {
  97.             return (int)(lower_bound(pts.begin(), pts.end(), v) - pts.begin());
  98.         };
  99.  
  100.         ParityDSU dsu(pts.size());
  101.  
  102.         // Process each query as constraint: prefix[l] XOR prefix[r+1] = v
  103.         for (auto& q : qs) {
  104.             int l = get(q[0]);
  105.             int r = get(q[1] + 1);
  106.             int v = (int)q[2];
  107.  
  108.             // Add constraint between prefix positions
  109.             if (!dsu.add(l, r, v)) {
  110.                 return false;  // Contradiction found
  111.             }
  112.         }
  113.  
  114.         return true;  // All constraints consistent
  115.     }
  116. };
  117.  
  118. int main() {
  119.     ios::sync_with_stdio(false);
  120.     cin.tie(nullptr);
  121.  
  122.     long long n;
  123.     int m;
  124.     cin >> n >> m;
  125.  
  126.     // Each query: [l, r, v] means XOR of range [l, r] equals v
  127.     vector<array<long long, 3>> qs(m);
  128.     for (int i = 0; i < m; i++) {
  129.         cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
  130.     }
  131.  
  132.     Solution sol;
  133.     bool ans = sol.check(n, qs);
  134.  
  135.     cout << (ans ? "YES" : "NO") << "\n";
  136.  
  137.     return 0;
  138. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/NeDI9H
language:
C++14 (gcc 8.3)
created:
3 hours 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!