This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int b = 1024;
map<int,pair<oset<int>,oset<int>>> blocks;
map<int,pair<oset<int>,oset<int>>> st;
inline void add(int l, int r) {
int pos = r / b;
blocks[pos].fi.insert(l);
blocks[pos].se.insert(-(r - l + 1));
st[r].fi.insert(l);
st[r].se.insert(-(r - l + 1));
}
inline void del(int l, int r) {
int pos = r / b;
blocks[pos].fi.erase(blocks[pos].fi.lower_bound(l - 1));
blocks[pos].se.erase(blocks[pos].se.lower_bound(-(r - l + 1) - 1));
if (!sz(blocks[pos].fi)) blocks.erase(pos);
st[r].fi.erase(st[r].fi.lower_bound(l - 1));
st[r].se.erase(st[r].se.lower_bound(-(r - l + 1) - 1));
if (!sz(st[r].fi)) st.erase(r);
}
inline int answer(int l, int r, int k) {
if (r - l + 1 < k) return 0;
int ans = 0;
int ps = (r + 1) / b;
auto it = blocks.upper_bound(ps);
while (it != blocks.end()) { ans += it->se.fi.order_of_key(r - k + 2); ++it; }
auto it1 = st.lower_bound(r + 1);
while (it1 != st.end() && it1->fi < (ps + 1) * b) { ans += it1->se.fi.order_of_key(r - k + 2); ++it1; }
{
l = l + k - 1;
int lb = l / b, rb = r / b;
if (lb == rb) {
it = st.lower_bound(l);
while (it != st.end() && it->fi <= r) {
ans += it->se.se.order_of_key(-k + 1);
++it;
}
}
else {
it = blocks.lower_bound(lb + 1);
while (it != blocks.end() && it->fi <= rb - 1) {
ans += it->se.se.order_of_key(-k + 1);
++it;
}
it = st.lower_bound(l);
while (it != st.end() && it->fi < (lb + 1) * b) {
ans += it->se.se.order_of_key(-k + 1);
++it;
}
it = st.lower_bound(rb * b);
while (it != st.end() && it->fi <= r) {
ans += it->se.se.order_of_key(-k + 1);
++it;
}
}
}
return ans;
}
inline void solve() {
int n, t;
cin >> n >> t;
int lid = 0;
ve<pii> segs(n);
int lst = 0;
while (n--) {
int e;
cin >> e;
if (e == 1) {
int l, r;
cin >> l >> r;
l ^= (t * lst);
r ^= (t * lst);
if (l > r) swap(l, r);
segs[lid++] = {l, r};
add(l, r);
}
else if (e == 2) {
int id;
cin >> id, --id;
del(segs[id].fi, segs[id].se);
}
else {
int l, r, k;
cin >> l >> r >> k;
l ^= (t * lst);
r ^= (t * lst);
if (l > r) swap(l, r);
lst = answer(l, r, k);
cout << lst << '\n';
}
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |