#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 = 4e2; /// cnt_of_blocks
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();
for (w = 0; w < L[q].size(); w++) {
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;
RS[q].clear();
R1[q].clear();
for (w = 0; w < R[q].size(); w++) {
RS[q][R[q][w].sz]++;
R1[q].insert(R[q][w].sz);
}
ll s = 0;
for (auto p : RS[q]){
RS[q][p.first] += s;
s = RS[q][p.first];
}
}
void rebuild() {
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;
}
if (q != 0) {
if (L[blocki].size() > block_sz) {
blocki++;
}
}
MNL[blocki] = min(MNL[blocki], segs[q].l);
MXL[blocki] = max(MXL[blocki], segs[q].l);
IL[q] = 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;
}
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]);
}
for (q = 0; q < block; q++) {
buildL(q);
}
for (q = 0; q < block; q++) {
buildR(q);
}
}
void add(seg a) {
a.i = S.size();
lasts.pb(a);
S.pb(a);
segs.pb(a);
IL[a.i] = IR[a.i] = -1;
}
void del(seg b) {
ll il = IL[b.i], ir = IR[b.i];
used[b.i] = 1;
if (il == -1) {
return;
}
cout << il << " " << ir << 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);
}
ll fastL(ll i, ll x) {
auto j = L1[i].upper_bound(x);
if (j == L1[i].begin()) {
return L[i].size();
}
j--;
ll ind = (*j);
ll dans = LS[i][ind];
ll ans = L[i].size() - dans;
return ans;
}
ll fastR(ll i, ll x) {
auto j = R1[i].upper_bound(x);
if (j == R1[i].begin()) {
return R[i].size();
}
j--;
ll ind = (*j);
ll dans = RS[i][ind];
ll ans = R[i].size() - dans;
return ans;
}
ll slowL(ll i, ll x, ll l) {
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 getansL(ll x, ll l) {
ll q;
ll ans = 0;
for (q = 0; q < block; q++) {
if (MNL[q] >= l) {
ans += fastL(q, x);
continue;
}
if (MXL[q] < l) {
continue;
}
if (MNL[q] < l) {
ans += slowL(q, x, l);
}
}
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;
ll ans = 0;
for (q = 0; q < block; q++) {
if (MXR[q] <= r) {
ans += fastR(q, x);
continue;
}
if (MNR[q] > r) {
continue;
}
if (MXR[q] > r) {
ans += slowR(q, x, r);
}
}
for (q = 0; q < lasts.size(); q++) {
if (used[lasts[q].i]) {
continue;
}
if (lasts[q].r <= r && lasts[q].sz >= x) {
ans++;
}
}
return ans;
}
ll answer(seg c, ll k) {
if (c.sz < k) {
return 0;
}
ll q, w;
ll lk = c.r - k + 2, rk = c.l + k - 2;
ll allans = getansR(0, inf);
ll dansl = getansL(k, lk);
ll dansr = getansR(k, rk);
ll 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 == 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]);
}
cout << "Q " << q << endl;
if (comm == 3) {
cin >> l >> r;
l ^= (lastans * t);
r ^= (lastans * t);
if (l > r) {
swap(l, r);
}
x.l = l; x.r = r;
cin >> c;
lastans = answer(x, c);
cout << lastans << 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:83: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:98: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:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < segs.size(); q++) {
~~^~~~~~~~~~~~~
segments.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (q = 0; q < segs.size(); q++) {
~~^~~~~~~~~~~~~
segments.cpp:110:8: warning: unused variable 'w' [-Wunused-variable]
ll q, w;
^
segments.cpp: In function 'll slowL(ll, ll, ll)':
segments.cpp:205: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:216: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:239: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:265: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:280:5: warning: unused variable 'q' [-Wunused-variable]
ll q, w;
^
segments.cpp:280:8: warning: unused variable 'w' [-Wunused-variable]
ll q, w;
^
segments.cpp: In function 'int main()':
segments.cpp:290:8: warning: unused variable 'w' [-Wunused-variable]
ll q, w, e, a, b, c;
^
segments.cpp:290:11: warning: unused variable 'e' [-Wunused-variable]
ll q, w, e, a, b, c;
^
segments.cpp:290:17: warning: unused variable 'b' [-Wunused-variable]
ll q, w, e, a, b, c;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2835 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
397 ms |
4984 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 |
1668 ms |
10056 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 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
