Submission #939468

#	Time	Username	Problem	Language	Result	Execution time	Memory
939468		AkibAzmain	Segments (IZhO18_segments)	C++17	0 / 100	697 ms	65536 KiB

segments

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using ll = long long;
using namespace __gnu_pbds;
template < class key, class compare = less < key > >
using iset = tree < key, null_type, compare, rb_tree_tag,
                    tree_order_statistics_node_update >;

void
solve (int tc, int ttc)
{
  ll q, t;
  cin >> q >> t;
  vector < pair < ll, ll > > v = { { -1, -1 } };
  ll sts = 1ll << 32ll;
  map < ll, ll > stl, str;
  ll las = 0;
  ll tsc = 0;
  while (q--)
    {
      int o;
      cin >> o;
      if (o == 1)
        {
          ll x, y;
          cin >> x >> y;
          x ^= t * las;
          y ^= t * las;
          if (x > y) swap (x, y);
          v.push_back ({ x, y });
          ll si = sts + x;
          while (si) ++stl[si], si /= 2;
          si = sts + y;
          while (si) ++str[si], si /= 2;
          ++tsc;
        }
      else if (o == 2)
        {
          int id;
          cin >> id;
          ll si = sts + v[id].first;
          while (si) --stl[si], si /= 2;
          si = sts + v[id].second;
          while (si) --str[si], si /= 2;
          --tsc;
        }
      else
        {
          auto stm = [&] (ll l, ll r, auto &st)
          {
            l += sts;
            r += sts;
            ll ans = 0;
            while (l <= r)
              {
                if (l % 2 == 1)
                  {
                    if (st.count (l)) ans += st[l];
                    ++l;
                  }
                if (r % 2 == 0)
                  {
                    if (st.count (r)) ans += st[r];
                    --r;
                  }
                l /= 2;
                r /= 2;
              }
            return ans;
          };
          ll x, y, k;
          cin >> x >> y >> k;
          x ^= t * las;
          y ^= t * las;
          if (x > y) swap (x, y);
          ll ans = tsc - stm (0, x - 1, str) - stm (y + 1, (ll) 2e9, stl);
          cout << ans << '\n';
          las = ans;
        }
    }
}

int
main ()
{
  ios::sync_with_stdio (false);
  cin.tie (nullptr);
  int ttc = 1;
  // cin >> ttc;
  for (int tc = 1; tc <= ttc; ++tc) solve (tc, ttc);
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25