#include <bits/stdc++.h>
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
using namespace std;
//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(time(0));
#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long
const int N = 2e5 + 100;
const int M = 31;
const int mod = 998244353;
const int inf = 1e9 + 7;
const int sq = 1000;
vector < pair < int, int > > c[N], d[N];
vector < pair < pair < int, int >, int > > b, all;
int pref[N / sq][sq + 1], suf[N / sq][sq + 1];
int mn[N], mx[N], uk, used[N], pos[N];
bool comp(pair < pair < int, int >, int > a, pair < pair < int, int >, int > b)
{
return (a.F.S - a.F.F < b.F.S - b.F.F);
}
void add(int l, int r, int id)
{
used[id] = 1;
pos[id] = -1;
b.pb({{l, r}, id});
all.pb({{l, r}, id});
if (sz(b) != sq) return;
sort(all.begin(), all.end(), comp);
for(int j = 0; j < uk; j++)
{
c[j].clear();
d[j].clear();
mn[j] = inf; mx[j] = -inf;
}
for(int i = 0; i < sz(all); i++)
{
int j = i / sq;
c[j].pb({all[i].F.F, all[i].S});
d[j].pb({all[i].F.S, all[i].S});
pos[all[i].S] = j;
mn[j] = min(mn[j], all[i].F.S - all[i].F.F + 1);
mx[j] = max(mx[j], all[i].F.S - all[i].F.F + 1);
}
for(int j = 0; j < uk; j++)
{
sort(c[j].begin(), c[j].end());
sort(d[j].begin(), d[j].end());
for(int z = sz(c[j]) - 1; z >= 0; z--)
{
if (z + 1 < sz(c[j])) suf[j][z] = suf[j][z + 1];
else suf[j][z] = 0;
suf[j][z] += used[c[j][z].S];
}
for(int z = 0; z < sz(c[j]); z++)
{
if (z) pref[j][z] = pref[j][z - 1];
else pref[j][z] = 0;
pref[j][z] += used[d[j][z].S];
}
}
uk++;
b.clear();
}
void del(int l, int r, int id)
{
used[id] = 0;
if (pos[id] == -1) return;
int j = pos[id];
for(int z = sz(c[j]) - 1; z >= 0; z--)
{
if (z + 1 < sz(c[j])) suf[j][z] = suf[j][z + 1];
else suf[j][z] = 0;
suf[j][z] += used[c[j][z].S];
}
for(int z = 0; z < sz(c[j]); z++)
{
if (z) pref[j][z] = pref[j][z - 1];
else pref[j][z] = 0;
pref[j][z] += used[d[j][z].S];
}
}
int get(int l, int r, int k)
{
if (r - l + 1 < k) return 0;
int ans = sz(all) - sz(b);
for(auto to: b)
if (used[to.S]) ans += (min(to.F.S, r) - max(to.F.F, l) + 1 >= k);
for(int j = 0; j < uk; j++)
{
if (mx[j] < k)
{
ans -= sq;
continue;
}
if (mn[j] < k)
{
for(int i = j * sq; i < (j + 1) * sq; i++)
{
if (!used[all[i].S]) continue;
auto to = all[i];
ans -= (min(to.F.S, r) - max(to.F.F, l) + 1 < k);
}
continue;
}
int le = 0, ri = sz(c[j]) - 1, gr = sz(c[j]);
while (le <= ri)
{
int mid = (le + ri) / 2;
if (c[j][mid].F > r - k + 1)
{
gr = mid;
ri = mid - 1;
}
else le = mid + 1;
}
if (gr < sz(c[j])) ans -= suf[j][gr];
le = 0; ri = sz(d[j]) - 1; int gl = sz(d[j]);
while (le <= ri)
{
int mid = (le + ri) / 2;
if (d[j][mid].F < l + k - 1)
{
gl = mid;
le = mid + 1;
}
else ri = mid - 1;
}
if (gl < sz(d[j])) ans -= pref[j][gl];
}
return ans;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif // LOCAL
int q, T;
cin >> q >> T;
vector < pair < int, int > > a;
int ans = 0;
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int l, r;
cin >> l >> r;
l = (l ^ (T * ans));
r = (r ^ (T * ans));
if (l > r) swap(l, r);
add(l, r, sz(a));
a.pb({l, r});
}
if (type == 2)
{
int id;
cin >> id; id--;
int l = a[id].F, r = a[id].S;
del(l, r, id);
}
if (type == 3)
{
int l, r, k;
cin >> l >> r >> k;
l = (l ^ (T * ans));
r = (r ^ (T * ans));
if (l > r) swap(l, r);
ans = get(l, r, k);
cout << ans << endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9968 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
805 ms |
14332 KB |
Output is correct |
| 2 |
Correct |
824 ms |
15232 KB |
Output is correct |
| 3 |
Correct |
799 ms |
15580 KB |
Output is correct |
| 4 |
Correct |
850 ms |
15552 KB |
Output is correct |
| 5 |
Correct |
1172 ms |
16988 KB |
Output is correct |
| 6 |
Correct |
1151 ms |
17000 KB |
Output is correct |
| 7 |
Correct |
805 ms |
15288 KB |
Output is correct |
| 8 |
Correct |
818 ms |
15260 KB |
Output is correct |
| 9 |
Correct |
831 ms |
15292 KB |
Output is correct |
| 10 |
Correct |
589 ms |
14116 KB |
Output is correct |
| 11 |
Correct |
584 ms |
14424 KB |
Output is correct |
| 12 |
Correct |
917 ms |
16056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
13676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
13512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9968 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9676 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9676 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
9968 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
