이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define all(v) v.begin(), v.end()
#define mp make_pair
#define pii pair<int, int>
#define f first
#define s second
const int mx = 2e5 + 5, sq = 888, mxBL = mx / sq + 5, inf = 1e9;
int n, t, idcnt, lans; pii segs[mx];
bool cmp(pii a, pii b){
return a.s > b.s or (a.s == b.s and a.f > b.f);
}
void get(int &a, int &b){
a ^= (lans * t); b ^= (lans * t);
if (a > b) swap(a, b);
}
struct DS{
int bl, lowsz[mxBL]; vector<pii> L[mxBL], R[mxBL]; vector<pii> newElem;
void rebuild(){
int tot = 0; map<int, vector<pii>> allSeg;
FOR(i, 0, bl + 1) for (pii X : L[i]) allSeg[X.s - X.f].push_back(X), tot++;
for (pii X : newElem) allSeg[X.s - X.f].push_back(X), tot++;
bl = 0; L[0].clear(); R[0].clear(); newElem.clear();
if (!allSeg.empty()) lowsz[0] = allSeg.begin()->f;
for (auto V : allSeg) for (pii X : V.s){
if (L[bl].size() >= sq){
bl++; lowsz[bl] = V.f;
L[bl].clear(), R[bl].clear();
}
L[bl].push_back(X); R[bl].push_back(X);
}
FOR(i, 0, bl + 1){
sort(L[i].begin(), L[i].end());
sort(R[i].begin(), R[i].end(), cmp);
}
}
void upd(int a, int b){
newElem.push_back(mp(a, b));
}
int qry(int l, int r, int k){
int i = bl, ret = 0;
while (i and lowsz[i] >= k - 1){
int sz = L[i].size();
int badL = sz - (upper_bound(all(L[i]), mp(r - k + 1, inf)) - L[i].begin());
int badR = sz - (upper_bound(all(R[i]), mp(-inf, l + k - 1), [](pii v, pii a){ return cmp(v, a); }) - R[i].begin());
ret += sz - badL - badR;
i--;
}
for (pii X : L[i]) if (X.s - X.f >= k - 1) ret += (X.f <= r - k + 1) and (X.s >= l + k - 1);
for (pii X : newElem) if (X.s - X.f >= k - 1) ret += (X.f <= r - k + 1) and (X.s >= l + k - 1);
return ret;
}
}cur, rem;
int main(){
cin >> n >> t;
FOR(i, 0, n){
if (!(i % sq)) cur.rebuild(), rem.rebuild();
int type; cin >> type;
if (type == 1){
int a, b; cin >> a >> b; get(a, b);
cur.upd(a, b); segs[++idcnt] = mp(a, b);
}
if (type == 2){
int id; cin >> id;
rem.upd(segs[id].f, segs[id].s);
}
if (type == 3){
int a, b, k; cin >> a >> b >> k; get(a, b);
lans = cur.qry(a, b, k) - rem.qry(a, b, k);
cout<<lans<<"\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... |