/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5+1, MAGIC = 1200;
class TaskD {
int n, T, id[N];
pair<int,int> segs[N];
vector<pair<int,int> > fl, fr;
vector<vector<int> > tl, tr;
int get_r(int l, int r, int targ_r) {
int ret = 0;
for(l += fr.size(), r += fr.size() + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) {
auto it = lower_bound(tr[l].begin(), tr[l].end(), targ_r);
ret += it - tr[l].begin();
// cout << "get_r " << it - tr[l].begin() << ' ' << *(--it) << endl;
// for(int x: tr[l]) cout << x << ' ';
// cout << endl;
++l;
}
if(r & 1) {
--r;
auto it = lower_bound(tr[r].begin(), tr[r].end(), targ_r);
ret += it - tr[r].begin();
// cout << "get_r " << it - tr[r].begin() << ' ' << *(--it) << endl;
// for(int x: tr[r]) cout << x << ' ';
// cout << endl;
}
}
return ret;
}
int get_l(int l, int r, int targ_l) {
int ret = 0;
for(l += fl.size(), r += fl.size() + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) {
auto it = upper_bound(tl[l].begin(), tl[l].end(), targ_l);
ret += tl[l].end() - it;
++l;
}
if(r & 1) {
--r;
auto it = upper_bound(tl[r].begin(), tl[r].end(), targ_l);
ret += tl[r].end() - it;
}
}
return ret;
}
void build() {
tl.clear();
tr.clear();
tl.resize(2 * fl.size());
tr.resize(2 * fr.size());
sort(fl.begin(), fl.end());
sort(fr.begin(), fr.end());
for(int i = 0; i < fl.size(); i++) tl[fl.size() + i] = {fl[i].second};
for(int i = 0; i < fr.size(); i++) tr[fr.size() + i] = {fr[i].second};
for(int i = fl.size()-1; i >= 1; i--) {
merge(tl[i << 1].begin(), tl[i << 1].end(), tl[i << 1 | 1].begin(), tl[i << 1 | 1].end(),
back_inserter(tl[i]));
// cout << i << ' ';
// for(int x: tl[i]) cout << x << ' ';
// cout << endl;
}
for(int i = fr.size()-1; i >= 1; i--) {
merge(tr[i << 1].begin(), tr[i << 1].end(), tr[i << 1 | 1].begin(), tr[i << 1 | 1].end(),
back_inserter(tr[i]));
}
}
public:
void solve(istream &cin, ostream &cout) {
cin >> n >> T;
int lastans = 0, tick = 0, alive = 0;
for(int i = 0; i < N; i++) segs[i] = {-1, -1};
for(int i = 0, inst; i < n; i++) {
if(i % MAGIC == 0) {
fl.clear();
fr.clear();
for(int j = 0; j < i; j++) {
if(segs[id[j]].first == -1) continue;
int len = segs[id[j]].second - segs[id[j]].first + 1;
fl.emplace_back(len, segs[id[j]].first);
fr.emplace_back(len, segs[id[j]].second);
}
build();
}
cin >> inst;
if(inst == 1) {
int l, r;
cin >> l >> r;
l ^= T * lastans;
r ^= T * lastans;
if(l > r) swap(l, r);
id[i] = ++tick;
segs[id[i]] = {l, r};
++alive;
} else if(inst == 2) {
int id;
cin >> id;
segs[id] = {-1, -1};
--alive;
} else {
int l, r, k;
cin >> l >> r >> k;
l ^= T * lastans;
r ^= T * lastans;
if(l > r) swap(l, r);
lastans = 0;
if(r-l+1 < k) {
cout << lastans << '\n';
continue;
}
// outside block -> three cases
int idx = lower_bound(fl.begin(), fl.end(), make_pair(k, 0)) - fl.begin();
lastans += idx; // len < k
lastans += get_l(idx, fl.size() - 1, r - k + 1); // l[j] > r[i] - k[i] + 1 and len >= k
lastans += get_r(idx, fr.size() - 1, l + k - 1); // r[j] < l[i] + k[i] - 1 and len >= k
// within same block
for(int j = i-1; j >= 0 && j / MAGIC == i / MAGIC; j--) {
if(segs[id[j]].first != -1) {
lastans += min(segs[id[j]].second, r) - max(segs[id[j]].first, l) + 1 < k;
}
}
lastans = alive - lastans;
cout << lastans << '\n';
}
}
}
};
class Solver {
public:
void solve(std::istream& in, std::ostream& out) {
TaskD *obj = new TaskD();
obj->solve(in, out);
delete obj;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solver solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Compilation message
segments.cpp: In member function 'void TaskD::build()':
segments.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < fl.size(); i++) tl[fl.size() + i] = {fl[i].second};
~~^~~~~~~~~~~
segments.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < fr.size(); i++) tr[fr.size() + i] = {fr[i].second};
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2555 ms |
22708 KB |
Output is correct |
| 2 |
Correct |
2458 ms |
23060 KB |
Output is correct |
| 3 |
Correct |
2623 ms |
23004 KB |
Output is correct |
| 4 |
Correct |
2760 ms |
24644 KB |
Output is correct |
| 5 |
Correct |
3357 ms |
38256 KB |
Output is correct |
| 6 |
Correct |
3325 ms |
38888 KB |
Output is correct |
| 7 |
Correct |
2455 ms |
23000 KB |
Output is correct |
| 8 |
Correct |
2526 ms |
23016 KB |
Output is correct |
| 9 |
Correct |
2539 ms |
22908 KB |
Output is correct |
| 10 |
Correct |
1243 ms |
12804 KB |
Output is correct |
| 11 |
Correct |
1620 ms |
15252 KB |
Output is correct |
| 12 |
Correct |
3012 ms |
30332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
3320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
2808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
2680 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
