#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
/*
ll pw(ll a, ll b) {
ll ans = 1; while (b) {
while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
ans = (ans * a) % MOD, --b;
} return ans;
}
*/
const ll INF = 1e10;
const int MAXN = 210000;
const int SQ = 500;
const int MX = SQ * 2;
const int BL = MAXN / SQ + 2;
const int UPD = SQ;
struct seg {
ll l, r, k;
int gl, gr, gk;
int ds;
};
seg arr[MAXN];
int cid;
vector<int> gkk[BL];
vector<int> gll[BL];
vector<int> grr[BL];
ll sgl[BL];
ll sgr[BL];
ll sgk[BL];
int gks[BL];
int gls[BL];
int grs[BL];
int glr[BL][BL];
int glk[BL][BL];
int grl[BL][BL];
int grk[BL][BL];
int gkl[BL][BL];
int gkr[BL][BL];
int n, t;
int bl;
bool cmpl(int a, int b) {
return arr[a].l > arr[b].l;
}
bool cmpr(int a, int b) {
return arr[a].r < arr[b].r;
}
bool cmpk(int a, int b) {
return arr[a].k > arr[b].k;
}
int sum = 0;
void rebuild() {
int start = clock();
int cnt = 0;
vector<int> vv;
for (int i = 0; i < cid; ++i)
if (!arr[i].ds)
++cnt, vv.push_back(i);
for (int i = 0; i < bl; ++i) {
gkk[i].clear(), gll[i].clear(), grr[i].clear();
sgk[i] = sgl[i] = sgr[i] = INF;
gks[i] = gls[i] = grs[i] = 0;
for (int j = 0; j < bl; ++j)
glr[i][j] = glk[i][j] = grl[i][j] = grk[i][j] = gkl[i][j] = gkr[i][j] = 0;
}
bl = (cnt + SQ - 1) / SQ;
for (int i = 0; i < bl; ++i) {
sgk[i] = sgl[i] = sgr[i] = INF;
}
sort(vv.begin(), vv.end(), cmpl);
for (int i = 0; i < vv.size(); ++i) {
arr[vv[i]].gl = i / SQ;
}
sort(vv.begin(), vv.end(), cmpr);
for (int i = 0; i < vv.size(); ++i) {
arr[vv[i]].gr = i / SQ;
}
sort(vv.begin(), vv.end(), cmpk);
for (int i = 0; i < vv.size(); ++i) {
arr[vv[i]].gk = i / SQ;
}
for (int i = 0; i < cid; ++i) {
if (arr[i].ds)
continue;
gll[arr[i].gl].push_back(i);
grr[arr[i].gr].push_back(i);
gkk[arr[i].gk].push_back(i);
++gls[arr[i].gl];
++grs[arr[i].gr];
++gks[arr[i].gk];
sgl[arr[i].gl] = min(sgl[arr[i].gl], -arr[i].l);
sgr[arr[i].gr] = min(sgr[arr[i].gr], arr[i].r);
sgk[arr[i].gk] = min(sgk[arr[i].gk], -arr[i].k);
int a = arr[i].gl;
int b = arr[i].gr;
int c = arr[i].gk;
++glr[a][b], ++glk[a][c], ++grl[b][a], ++grk[b][c], ++gkl[c][a], ++gkr[c][b];
}
for (int i = 0; i < bl; ++i) {
for (int j = 0; j < bl - 1; ++j) {
glr[i][j + 1] += glr[i][j];
glk[i][j + 1] += glk[i][j];
grl[i][j + 1] += grl[i][j];
grk[i][j + 1] += grk[i][j];
gkl[i][j + 1] += gkl[i][j];
gkr[i][j + 1] += gkr[i][j];
}
}
sgk[0] = sgl[0] = sgr[0] = -INF;
bl = max(1, bl);
sum += clock() - start;
}
int main() {
scanf("%d%d", &n, &t);
int curans = 0;
int fll = 1;
for (int i = 0; i < n; ++i) {
if (fll) {
fll = 0;
rebuild();
}
int tp;
scanf("%d", &tp);
if (tp == 1) {
ll l, r;
scanf("%lld%lld", &l, &r);
l = l ^ (t * curans);
r = r ^ (t * curans);
if (l > r)
swap(l, r);
++r;
ll k = r - l;
arr[cid].l = l;
arr[cid].r = r;
arr[cid].k = r - l;
int a = 0, b = 0, c = 0;
while (a < bl && sgl[a] <= -l)
++a;
while (b < bl && sgr[b] <= r)
++b;
while (c < bl && sgk[c] <= -k)
++c;
a = max(0, a - 1), b = max(0, b - 1), c = max(0, c - 1);
arr[cid].gl = a;
arr[cid].gr = b;
arr[cid].gk = c;
++gls[a];
++grs[b];
++gks[c];
gll[a].push_back(cid);
grr[b].push_back(cid);
gkk[c].push_back(cid);
for (int i = b; i < bl; ++i)
++glr[a][i];
for (int i = c; i < bl; ++i)
++glk[a][i];
for (int i = a; i < bl; ++i)
++grl[b][i];
for (int i = c; i < bl; ++i)
++grk[b][i];
for (int i = a; i < bl; ++i)
++gkl[c][i];
for (int i = b; i < bl; ++i)
++gkr[c][i];
++cid;
}
else if (tp == 2) {
int id;
scanf("%d", &id);
--id;
arr[id].ds = 1;
int a = arr[id].gl;
int b = arr[id].gr;
int c = arr[id].gk;
--gls[a];
--grs[b];
--gks[c];
for (int i = b; i < bl; ++i)
--glr[a][i];
for (int i = c; i < bl; ++i)
--glk[a][i];
for (int i = a; i < bl; ++i)
--grl[b][i];
for (int i = c; i < bl; ++i)
--grk[b][i];
for (int i = a; i < bl; ++i)
--gkl[c][i];
for (int i = b; i < bl; ++i)
--gkr[c][i];
}
else {
ll x, y, k;
scanf("%lld%lld%lld", &x, &y, &k);
x = (x ^ (t * curans));
y = (y ^ (t * curans));
if (x > y)
swap(x, y);
++y;
if (y - x < k) {
curans = 0;
printf("0\n");
continue;
}
int a = 0, b = 0, c = 0;
int ans = 0;
while (c < bl && sgk[c] <= -k)
++c;
while (b < bl && sgr[b] < x + k)
++b;
while (a < bl && sgl[a] < k - y)
++a;
--a;
--b;
--c;
for (int i = 0; i < c; ++i) {
ans += gks[i];
if (a > 0)
ans -= gkl[i][a - 1];
if (b > 0)
ans -= gkr[i][b - 1];
}
if (gkk[c].size() > MX)
fll = 1;
if (gll[a].size() > MX)
fll = 1;
if (grr[b].size() > MX)
fll = 1;
for (int id: gkk[c]) {
if (arr[id].ds || arr[id].r < x + k || arr[id].l > y - k || arr[id].k < k)
continue;
++ans;
}
for (int id: gll[a]) {
if (!arr[id].ds && arr[id].l > y - k && arr[id].gk < c)
--ans;
}
if (b < bl) {
for (int id: grr[b]) {
if (!arr[id].ds && arr[id].r < x + k && arr[id].gk < c)
--ans;
}
}
printf("%d\n", ans);
curans = ans;
}
}
cerr << ld(sum) / CLOCKS_PER_SEC << "\n";
return 0;
}
Compilation message
segments.cpp: In function 'void rebuild()':
segments.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vv.size(); ++i) {
~~^~~~~~~~~~~
segments.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vv.size(); ++i) {
~~^~~~~~~~~~~
segments.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vv.size(); ++i) {
~~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &t);
~~~~~^~~~~~~~~~~~~~~~
segments.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &tp);
~~~~~^~~~~~~~~~~
segments.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~
segments.cpp:194:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &id);
~~~~~^~~~~~~~~~~
segments.cpp:218:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &x, &y, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
930 ms |
7656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
333 ms |
7656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
7656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
