제출 #485673

#제출 시각아이디문제언어결과실행 시간메모리
485673SirCovidThe19thSegments (IZhO18_segments)C++17
7 / 100
5086 ms20276 KiB
#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 = 1, 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; 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(); for (auto V : allSeg) for (pii X : V.s){ if (L[bl].size() >= sq) bl++, 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 L[i][0].s - L[i][0].f >= 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<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...