이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
const int maxN = 2e5 + 5, blockSz = 2000, maxCnt = (maxN + blockSz - 1) / blockSz;
int q, t, idSeg;
int l[maxN], r[maxN];
bool rem[maxN];
vector<ii> R;
int n, blockCnt;
int mnR[maxCnt], mxR[maxCnt];
vector<ii> Block[maxCnt]; // change sz
vector<ii> BlockL[maxCnt];
vector<ii> cur;
void reset() {
for (auto T : cur)
if (T.se)
rem[T.fi] = true;
R.clear(), cur.clear();
for (int i = 1; i <= idSeg; i++)
if (!rem[i])
R.pb({r[i], i});
sort(all(R));
n = R.size();
blockCnt = (n + blockSz - 1) / blockSz;
for (int b = 0; b <= blockCnt; b++) {
Block[b].clear();
BlockL[b].clear();
}
for (int b = 0; b < blockCnt; b++) {
for (int i = b * blockSz; i < min(n, (b + 1) * blockSz); i++) {
int id = R[i].se;
Block[b].pb({r[id] - l[id] + 1, r[id]});
BlockL[b].pb({l[id], r[id]});
mxR[b] = r[id];
if (i == b * blockSz)
mnR[b] = r[id];
}
sort(all(Block[b]));
sort(all(BlockL[b]));
}
}
int R_lessthan(int val) {
return lower_bound(all(R), mp(val, -1)) - R.begin();
}
int length_lessthan(int rr, int k) {
if (!blockCnt)
return 0;
int id = 0, ans = 0;
while (id < blockCnt && mxR[id] <= rr) {
ans += lower_bound(all(Block[id]), mp(k, -1)) - Block[id].begin();
id++;
}
for (auto T : Block[id])
if (T.se <= rr && T.fi < k)
ans++;
return ans;
}
int bruh(int ll, int rr) {
if (!blockCnt)
return 0;
int id = blockCnt - 1;
int ans = 0;
while (id > 0 && mnR[id] > rr) {
ans += (int)BlockL[id].size() - (upper_bound(all(BlockL[id]), mp(ll, INT_MAX)) - BlockL[id].begin());
id--;
}
for (auto T : BlockL[id])
if (T.fi > ll && T.se > rr)
ans++;
return ans;
}
int length_lessthan(int ll, int rr, int k) {
return length_lessthan(rr, k) - length_lessthan(ll - 1, k);
}
bool bad(int l1, int r1, int l2, int r2) { return r1 < l2 || r2 < l1; }
int query(int ll, int rr, int k) {
if (rr - ll + 1 < k)
return 0;
int ans = n;
ans -= (R_lessthan(ll + k - 1) + length_lessthan(ll + k - 1, rr, k) + bruh(rr - k + 1, rr));
if (ans < 0) {
assert(false);
}
for (auto T : cur)
if (!k || (!bad(l[T.fi], r[T.fi], ll, rr) && min(r[T.fi], rr) - max(l[T.fi], ll) + 1 >= k))
ans += (T.se ? -1 : 1);
return ans;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> q >> t;
for (int i = 1, lastAns = 0; i <= q; i++) {
if (!(i % blockSz))
reset();
int type; cin >> type;
if (type == 1) {
idSeg++; cin >> l[idSeg] >> r[idSeg];
l[idSeg] ^= t * lastAns;
r[idSeg] ^= t * lastAns;
if (l[idSeg] > r[idSeg])
swap(l[idSeg], r[idSeg]);
cur.pb({idSeg, 0});
}
else if (type == 2) {
int remId; cin >> remId;
cur.pb({remId, 1});
}
else {
int ll, rr, k; cin >> ll >> rr >> k;
ll ^= t * lastAns;
rr ^= t * lastAns;
if (ll > rr)
swap(ll, rr);
cout << (lastAns = query(ll, rr, k)) << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |