| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 593175 | Zanite | Segments (IZhO18_segments) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// I am now here, but I have yet to prove that I am worthy of my place here.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
int n, t, lastans;
vector<pii> segments(1);
int sqrtn;
inline const bool comp(const pii &a,const pii &b) {return ((a.se - a.fi) > (b.se - b.fi));}
inline int intersect(pii a, pii b) {return max(0, min(a.se, b.se) - max(a.fi, b.fi) + 1);}
inline int findLess(vector<int> &v, int x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}
struct DelayedVector {
vector<pii> pending, saved;
vector<int> len;
vector<vector<int>> left, right;
DelayedVector() {}
void rebuild() {
sort(pending.begin(), pending.end(), comp);
vector<pii> temp;
int i = 0, j = 0;
for (; i < (int)pending.size() && j < (int)saved.size(); ) {
if (comp(pending[i], saved[j])) {
temp.push_back(pending[i]);
i++;
} else {
temp.push_back(saved[j]);
j++;
}
}
for (; i < (int)pending.size(); i++) temp.push_back(pending[i]);
for (; j < (int)saved.size(); j++) temp.push_back(saved[j]);
pending.clear();
saved = temp;
// recompute lengths
len.clear();
for (auto &[l, r] : saved) {len.push_back(r - l + 1);}
// recompute blocks
left.clear(); right.clear();
left.push_back({}); right.push_back({});
for (int ptr = 0, i = 0; i < (int)saved.size(); i++) {
left[ptr].push_back(saved[i].fi);
right[ptr].push_back(saved[i].se);
if ((int)left[ptr].size() >= sqrtn) {
ptr++;
left.push_back({}); right.push_back({});
}
}
if (left.back().empty()) {left.pop_back();}
if (right.back().empty()) {right.pop_back();}
for (auto &i : left) {sort(i.begin(), i.end());}
for (auto &i : right) {sort(i.begin(), i.end());}
}
void update(int l, int r) {
pending.push_back({l, r});
// rebuild the sqrt decomposition
if ((int)pending.size() > sqrtn) {rebuild();}
}
int query(int k, int l, int r) {
// a segment [x, y] does not have at least k points in common with [l, r] if
// x > (r - (k - 1)) || y < (l + (k - 1))
if (k > (r - l + 1)) return 0;
int ans = 0;
pii segment = {l, r};
for (auto &p : pending) {
if (intersect(segment, p) >= k) {ans++;}
}
int st = 0;
for (int i = 0; i < (int)left.size(); st += (int)left[i].size(), i++) {
assert_WA(st < (int)saved.size());
assert_WA(st + (int)left[i].size() - 1 < (int)saved.size());
if (len[st + (int)left[i].size() - 1] >= k) {
ans += findLess(left[i], r - (k-1) + 1);
ans -= findLess(right[i], l + (k-1));
} else if (len[st] >= k) {
for (int j = st; j < st + (int)left[i].size(); j++) {
if (intersect(segment, saved[j]) >= k) {ans++;}
}
} else break;
}
return ans;
}
};
int main() {
scanf("%d %d", &n, &t);
sqrtn = sqrt(n);
DelayedVector All, Deleted;
for (int typ, a, b, k, id, i = 1; i <= n; i++) {
scanf("%d", &typ);
if (typ == 1) {
scanf("%d %d", &a, &b);
a ^= (t * lastans);
b ^= (t * lastans);
if (a > b) {swap(a, b);}
segments.push_back({a, b});
All.update(a, b);
} else if (typ == 2) {
scanf("%d", &id);
assert(id < segments.size());
Deleted.update(segments[id].fi, segments[id].se);
} else {
scanf("%d %d %d", &a, &b, &k);
a ^= (t * lastans);
b ^= (t * lastans);
if (a > b) {swap(a, b);}
lastans = All.query(k, a, b) - Deleted.query(k, a, b);
printf("%d\n", lastans);
}
}
}