#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define MOMI using namespace std;
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma optimize("TKACHENKO-GORYACHENKO")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll inf = 1e15;
const ll maxn = 3e5;
const ll block = 1e3; /// cnt_of_blocks
// const ll block_sz = 5e3 + 10;
const ll block_sz = (maxn + block - 1) / block;
ll n, m, k, t;
struct seg{
ll l;
ll r;
ll sz;
ll i;
};
bool operator==(seg a, seg b) {
return a.i == b.i;
}
vector <seg> S;
vector <seg> segs;
vector <seg> lasts;
bool cmp(seg a, seg b) {
return (a.r - a.l) < (b.r - b.l);
}
bool cmpl(seg a, seg b) {
return a.l < b.l;
}
bool cmpr(seg a, seg b) {
return a.r < b.r;
}
ll LASTL[block];
ll LASTR[block];
vector <seg> R[block];
vector <seg> L[block];
set <ll> L1[block];
set <ll> R1[block];
map <ll, ll> LS[block];
map <ll, ll> RS[block];
ll MNL[block];
ll MXL[block];
ll MNR[block];
ll MXR[block];
ll IL[maxn];
ll IR[maxn];
bool used[maxn];
void buildL(ll q) {
ll w;
LS[q].clear();
L1[q].clear();
MNL[q] = inf;
MXL[q] = -inf;
for (w = 0; w < L[q].size(); w++) {
MNL[q] = min(MNL[q], L[q][w].l);
MXL[q] = max(MXL[q], L[q][w].l);
LS[q][L[q][w].sz]++;
L1[q].insert(L[q][w].sz);
}
ll s = 0;
for (auto p : LS[q]) {
LS[q][p.first] += s;
s = LS[q][p.first];
}
}
void buildR(ll q) {
ll w;
if (R[q].size() == 0) {
return;
}
MNR[q] = -inf;
MXR[q] = inf;
RS[q].clear();
R1[q].clear();
for (w = 0; w < R[q].size(); w++) {
MNR[q] = min(MNR[q], R[q][w].r);
MXR[q] = max(MXR[q], R[q][w].r);
// cout << R[q][w].sz << " ";
RS[q][R[q][w].sz] += 1;
R1[q].insert(R[q][w].sz);
}
// cout << endl;
ll s = 0;
for (auto p : RS[q]){
RS[q][p.first] += s;
s = RS[q][p.first];
}
// for (auto p: RS[q]) {
// cout << p.first << " " << p.second << endl;
// }
// cout << endl << endl;
}
void rebuild() {
// cout << "VSEM PIZDEC " << endl << endl << endl;
ll q, w;
lasts.clear();
ll blocki = 0;
for (q = 0; q < block; q++) {
MNL[q] = inf;
MXL[q] = -inf;
MNR[q] = inf;
MXR[q] = -inf;
}
sort(segs.begin(), segs.end(), cmpl);
for (q = 0; q < segs.size(); q++) {
if (used[segs[q].i]) {
continue;
}
L[q].clear();
if (q != 0) {
if (L[blocki].size() > block_sz) {
blocki++;
}
}
//cout << "BLOCKI " << blocki << " " << segs[q].l << endl;
MNL[blocki] = min(MNL[blocki], segs[q].l);
MXL[blocki] = max(MXL[blocki], segs[q].l);
IL[segs[q].i] = blocki;
L[blocki].pb(segs[q]);
}
sort(segs.begin(), segs.end(), cmpr);
for (q = 0; q < segs.size(); q++) {
if (used[segs[q].i]) {
continue;
}
R[q].clear();
// cout << "NOT USED " << segs[q].i << endl;
if (q != 0) {
if (R[blocki].size() > block_sz) {
blocki++;
}
}
MNR[blocki] = min(MNR[blocki], segs[q].r);
MXR[blocki] = max(MXR[blocki], segs[q].r);
IR[segs[q].i] = blocki;
R[blocki].pb(segs[q]);
}
// cout << "SZ UMOM " << R[0].size() << endl;
for (q = 0; q < block; q++) {
buildL(q);
}
for (q = 0; q < block; q++) {
buildR(q);
}
}
void add(seg a) {
lasts.pb(a);
S.pb(a);
segs.pb(a);
IL[a.i] = IR[a.i] = -1;
}
void del(seg b) {
// cout << b.i << " I" << endl;
ll il = IL[b.i], ir = IR[b.i];
used[b.i] = 1;
if (il == -1) {
return;
}
// cout << il << " " << ir << endl;
ll sz = R[ir].size();
//cout << "IR " << ir << " " << sz << endl;
L[il].erase(find(L[il].begin(), L[il].end(), b));
R[ir].erase(find(R[ir].begin(), R[ir].end(), b));
buildL(il);
buildR(ir);
// cout << "NEW SZ " << R[ir].size() << endl << endl;
if (R[ir].size() == sz) {
//cout << "UH SYKA" << endl;
}
}
ll slowL(ll i, ll x, ll l) {
//cout << "SLOW CARS" << endl;
ll q;
ll ans = 0;
for (q = 0; q < L[i].size(); q++) {
if (L[i][q].l >= l && L[i][q].sz >= x) {
ans++;
}
}
return ans;
}
ll slowR(ll i, ll x, ll r) {
ll q;
ll ans = 0;
for (q = 0; q < R[i].size(); q++) {
if (R[i][q].r <= r && R[i][q].sz >= x) {
ans++;
}
}
return ans;
}
ll fastL(ll i, ll x) {
auto j = L1[i].lower_bound(x);
if (j == L1[i].begin()) {
return L[i].size();
}
// for (ll q = 0; q < L[i].size(); q++) {
// cout << L[i][q].sz << " ";
// }
// cout << endl;
// cout << endl << endl;
j--;
ll ind = (*j);
ll dans = LS[i][ind];
ll ans = L[i].size() - dans;
//cout << ans << endl;
return ans;
}
ll fastR(ll i, ll x) {
auto j = R1[i].lower_bound(x);
if (j == R1[i].begin()) {
return R[i].size();
}
// for (ll q = 0; q < L[i].size(); q++) {
// cout << L[i][q].sz << " ";
// }
// cout << endl;
// cout << endl << endl;
j--;
ll ind = (*j);
// cout << "IND " << ind << endl;
ll dans = RS[i][ind];
ll ans = R[i].size() - dans;
return ans;
}
ll getansL(ll x, ll l) {
ll q;
// cout << "L " << l << endl;
ll ans = 0;
for (q = 0; q < block; q++) {
// if (MNL[q] != inf)cout << MNL[q] << " " << MXL[q] << " " << q << " MNL" << endl;
if (MNL[q] == inf) {
continue;
}
if (MNL[q] >= l) {
ans += fastL(q, x);
continue;
}
if (MXL[q] < l) {
// cout << "UMOM " << endl;
continue;
}
if (MNL[q] < l) {
ans += slowL(q, x, l);
}
}
// if (ans != 0) {
// exit(-1);
// }
for (q = 0; q < lasts.size(); q++) {
if (used[lasts[q].i]) {
continue;
}
if (lasts[q].l >= l && lasts[q].sz >= x) {
ans++;
}
}
return ans;
}
ll getansR(ll x, ll r) {
ll q;
//cout << "X R " << x << " " << r << endl;
ll ans = 0;
for (q = 0; q < block; q++) {
// if (R[q].size() != 0)cout << "SZ " << R[q].size() << " " << q << endl;
if (MNR[q] == inf) {
continue;
}
if (MXR[q] <= r) {
ll dans = fastR(q, x);
// cout << "DANS1 " << q << " " << dans << endl;
ans += dans;
continue;
}
if (MNR[q] > r) {
continue;
}
if (MXR[q] > r) {
ll dans = slowR(q, x, r);
// cout << "DANS2 " << q << " " << dans << endl;
ans += dans;
}
}
for (q = 0; q < lasts.size(); q++) {
if (used[lasts[q].i]) {
continue;
}
if (lasts[q].r <= r && lasts[q].sz >= x) {
// cout << "DANS3 " << lasts[q].i << " " << 1 << endl;
ans++;
}
}
// cout << "ANS " << ans << endl << endl;
return ans;
}
ll answer(seg c, ll k) {
if (c.sz < k) {
return 0;
}
ll q, w;
ll ans = 0;
// for (q = 0; q < lasts.size(); q++) {
// if (used[lasts[q].i]) {
// continue;
// }
// ll li = max(lasts[q].l, c.l), ri = min(lasts[q].r, c.r);
// if (ri - li + 1 >= k) {
// ans++;
// }
// }
// return ans;
ll lk = c.r - k + 2, rk = c.l + k - 2;
ll allans = getansR(k, inf);
ll dansl = getansL(k, lk);
// cout << "SMERT" << endl;
ll dansr = getansR(k, rk);
// cout << "DEBUG " << allans << " " << dansl << " " << dansr << endl;
ans = allans - dansr - dansl;
return ans;
}
signed main() {
ll q, w, e, a, b, c;
cin >> n >> t;
ll lastans = 0;
for (q = 0; q < n; q++) {
ll comm;
if (q % block_sz == 0) {
rebuild();
}
cin >> comm;
ll l, r;
seg x;
if (comm == 1) {
cin >> l >> r;
l ^= (lastans * t);
r ^= (lastans * t);
if (l > r) {
swap(l, r);
}
x.l = l; x.r = r;
x.sz = r - l + 1;
x.i = segs.size();
add(x);
}
if (comm == 2) {
cin >> a;
a--;
del(S[a]);
}
if (comm == 3) {
cin >> l >> r;
l ^= (lastans * t);
r ^= (lastans * t);
if (l > r) {
swap(l, r);
}
x.l = l; x.r = r;
x.sz = x.r - x.l + 1;
cin >> c;
lastans = answer(x, c);
cout << lastans << endl;
}
// cout << "Q " << q << endl;
}
return 0;
}
Compilation message
segments.cpp:7:0: warning: ignoring #pragma optimize [-Wunknown-pragmas]
#pragma optimize("TKACHENKO-GORYACHENKO")
segments.cpp: In function 'void buildL(ll)':
segments.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (w = 0; w < L[q].size(); w++) {
~~^~~~~~~~~~~~~
segments.cpp: In function 'void buildR(ll)':
segments.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (w = 0; w < R[q].size(); w++) {
~~^~~~~~~~~~~~~
segments.cpp: In function 'void rebuild()':
segments.cpp:139:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < segs.size(); q++) {
~~^~~~~~~~~~~~~
segments.cpp:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < segs.size(); q++) {
~~^~~~~~~~~~~~~
segments.cpp:129:8: warning: unused variable 'w' [-Wunused-variable]
ll q, w;
^
segments.cpp: In function 'void del(seg)':
segments.cpp:203:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (R[ir].size() == sz) {
~~~~~~~~~~~~~^~~~~
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:212:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < L[i].size(); q++) {
~~^~~~~~~~~~~~~
segments.cpp: In function 'll slowR(ll, ll, ll)':
segments.cpp:223:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < R[i].size(); q++) {
~~^~~~~~~~~~~~~
segments.cpp: In function 'll getansL(ll, ll)':
segments.cpp:292:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < lasts.size(); q++) {
~~^~~~~~~~~~~~~~
segments.cpp: In function 'll getansR(ll, ll)':
segments.cpp:327:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < lasts.size(); q++) {
~~^~~~~~~~~~~~~~
segments.cpp: In function 'll answer(seg, ll)':
segments.cpp:344:5: warning: unused variable 'q' [-Wunused-variable]
ll q, w;
^
segments.cpp:344:8: warning: unused variable 'w' [-Wunused-variable]
ll q, w;
^
segments.cpp: In function 'int main()':
segments.cpp:367:8: warning: unused variable 'w' [-Wunused-variable]
ll q, w, e, a, b, c;
^
segments.cpp:367:11: warning: unused variable 'e' [-Wunused-variable]
ll q, w, e, a, b, c;
^
segments.cpp:367:17: warning: unused variable 'b' [-Wunused-variable]
ll q, w, e, a, b, c;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
1656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
1524 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Incorrect |
31 ms |
888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
