| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 339770 | GioChkhaidze | Segments (IZhO18_segments) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 2e9 + 1;
const int N = 2e5 + 5;
const int Sq = 6666;
unordered_map < int , int > G;
vector < int > v[Sq][3];
int a[N][3], pr[N][3], c[N], A[N], L[Sq][3], R[Sq][3];
int n, t, tot, del, mid, res, ret, lo, hi, sq, ms, as, tp, id, y, bl, j, k, x;
bool cmp1(int x, int y) {
return a[x][tp] < a[y][tp];
}
bool cmp2(int x, int y) {
return c[x] < c[y];
}
inline void Restart() {
for (tp = 0; tp < 2; ++tp) {
as = 0;
for (bl = 0; bl < ms; ++bl) {
for (j = 0; j < v[bl][tp].size(); ++j)
A[as] = v[bl][tp][j], ++as;
v[bl][tp].clear();
}
if (as) sort(A , A + as, cmp1);
for (j = 0; j < as; ++j) {
v[(j / sq)][tp].push_back(A[j]);
pr[A[j]][tp] = (j / sq);
}
for (bl = 0; bl < ms; ++bl) {
if (!v[bl][tp].size()) continue;
R[bl][tp] = -inf, L[bl][tp] = inf;
sort(v[bl][tp].begin(), v[bl][tp].end(), cmp2);
for (j = 0; j < v[bl][tp].size(); ++j) {
y = a[v[bl][tp][j]][tp];
if (R[bl][tp] < y) R[bl][tp] = y;
if (L[bl][tp] > y) L[bl][tp] = y;
}
}
}
}
inline void p() {
k = c[id], x = a[id][tp];
for (bl = 0; bl < ms; ++bl)
if (!v[bl][tp].size() || x <= R[bl][tp]) {
if (!v[bl][tp].size()) R[bl][tp] = L[bl][tp] = x;
pr[id][tp] = bl;
v[bl][tp].push_back(id);
j = v[bl][tp].size()-1;
while (0 < j && c[v[bl][tp][j-1]] > k)
swap(v[bl][tp][j-1], v[bl][tp][j]), --j;
if (x < L[bl][tp]) L[bl][tp] = x;
return ;
}
}
inline void d() {
k = c[id], x = a[id][tp];
for (bl = 0; bl < ms; ++bl)
if (pr[id][tp] == bl) {
for (j = 0; j + 1 < v[bl][tp].size(); ++j)
if (v[bl][tp][j] == id) swap(v[bl][tp][j], v[bl][tp][j + 1]);
assert(v[bl][tp].back()==id);
v[bl][tp].pop_back();
if (v[bl][tp].size()) {
R[bl][tp] = -inf, L[bl][tp] = inf;
for (j = 0; j < v[bl][tp].size(); ++j) {
y = a[v[bl][tp][j]][tp];
if (R[bl][tp] < y) R[bl][tp] = y;
if (L[bl][tp] > y) L[bl][tp] = y;
}
}
return ;
}
}
int br;
int g(int l, int r, int k) {
if (l > r) return 0;
ret = 0;
for (bl = 0; bl < ms; ++bl) {
if (!v[bl][tp].size() || R[bl][tp] < l || r < L[bl][tp]) continue;
if (l <= L[bl][tp] && R[bl][tp] <= r) {
lo = 0, hi = v[bl][tp].size() - 1, res = 0;
while (lo <= hi) {
mid = ((lo + hi) >> 1);
if (c[v[bl][tp][mid]] < k)
res = lo = mid + 1;
else
hi = mid - 1;
}
ret += v[bl][tp].size() - res;
}
else {
for (j = 0; j < v[bl][tp].size(); ++j) {
id = v[bl][tp][j];
if (c[id] < k) continue;
if (tp && a[id][1] <= r) ++ret;
if (!tp && l <= a[id][0]) ++ret;
}
}
}
return ret;
}
void up(ll x) {
while (x <= inf) {
G[x] += del;
x += (x & -x);
}
}
int gt(ll x) {
res = 0;
while (x > 0) {
res += G[x];
x -= (x & -x);
}
return res;
}
main () {
scanf("%d %d",&n, &t);
sq = sqrt(4*n);
ms = (n - 1 + sq - 1) / sq;
int lastans = 0, ans = 0, cnt = 0, u = 0, idx, ty, X, Y, Z, A, B, C;
for (int i = 0; i < n; ++i) {
if (!(i % sq)) Restart();
scanf("%d",&ty);
if (ty == 1) {
id = ++u, ++cnt;
scanf("%d %d",&a[u][0], &a[u][1]);
a[u][0] = (a[u][0] ^ (t * lastans));
a[u][1] = (a[u][1] ^ (t * lastans));
if (a[u][0] > a[u][1]) swap(a[u][0], a[u][1]);
c[u] = (a[u][1] - a[u][0] + 1);
tp = 0, p();
tp = 1, p();
del = 1, up(c[u]);
}
else
if (ty == 2) {
scanf("%d",&idx); --cnt, id = idx;
tp = 0, d();
tp = 1, d();
del = -1, up(c[id]);
}
else
if (ty == 3) {
scanf("%d %d %d",&A, &B, &C);
A = (A ^ (t * lastans));
B = (B ^ (t * lastans));
if (A > B) swap(A, B);
if (B - A + 1 < C) lastans = ans = 0;
else {
tp = 0, X = g(B - C + 2, 2e9, C);
tp = 1, Y = g(0, A + C - 2, C);
Z = gt(C - 1);
lastans = ans = cnt - (X + Y + Z);
}
printf("%d\n",ans);
}
}
}#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 2e9 + 1;
const int N = 2e5 + 5;
const int Sq = 6666;
map < int , int > G;
vector < int > v[Sq][3];
int a[N][3], pr[N][3], c[N], A[N], L[Sq][3], R[Sq][3];
int n, t, tot, del, mid, res, ret, lo, hi, sq, ms, as, tp, id, y, bl, j, k, x;
bool cmp1(int x, int y) {
return a[x][tp] < a[y][tp];
}
bool cmp2(int x, int y) {
return c[x] < c[y];
}
inline void Restart() {
for (tp = 0; tp < 2; ++tp) {
as = 0;
for (bl = 0; bl < ms; ++bl) {
for (j = 0; j < v[bl][tp].size(); ++j)
A[as] = v[bl][tp][j], ++as;
v[bl][tp].clear();
}
if (as) sort(A , A + as, cmp1);
for (j = 0; j < as; ++j) {
v[(j / sq)][tp].push_back(A[j]);
pr[A[j]][tp] = (j / sq);
}
for (bl = 0; bl < ms; ++bl) {
if (!v[bl][tp].size()) continue;
R[bl][tp] = -inf, L[bl][tp] = inf;
sort(v[bl][tp].begin(), v[bl][tp].end(), cmp2);
for (j = 0; j < v[bl][tp].size(); ++j) {
y = a[v[bl][tp][j]][tp];
if (R[bl][tp] < y) R[bl][tp] = y;
if (L[bl][tp] > y) L[bl][tp] = y;
}
}
}
}
inline void p() {
k = c[id], x = a[id][tp];
for (bl = 0; bl < ms; ++bl)
if (!v[bl][tp].size() || x <= R[bl][tp]) {
if (!v[bl][tp].size()) R[bl][tp] = L[bl][tp] = x;
pr[id][tp] = bl;
v[bl][tp].push_back(id);
j = v[bl][tp].size()-1;
while (0 < j && c[v[bl][tp][j-1]] > k)
swap(v[bl][tp][j-1], v[bl][tp][j]), --j;
if (x < L[bl][tp]) L[bl][tp] = x;
return ;
}
}
inline void d() {
k = c[id], x = a[id][tp];
for (bl = 0; bl < ms; ++bl)
if (pr[id][tp] == bl) {
for (j = 0; j + 1 < v[bl][tp].size(); ++j)
if (v[bl][tp][j] == id) swap(v[bl][tp][j], v[bl][tp][j + 1]);
assert(v[bl][tp].back()==id);
v[bl][tp].pop_back();
if (v[bl][tp].size()) {
R[bl][tp] = -inf, L[bl][tp] = inf;
for (j = 0; j < v[bl][tp].size(); ++j) {
y = a[v[bl][tp][j]][tp];
if (R[bl][tp] < y) R[bl][tp] = y;
if (L[bl][tp] > y) L[bl][tp] = y;
}
}
return ;
}
}
int br;
int g(int l, int r, int k) {
if (l > r) return 0;
ret = 0;
for (bl = 0; bl < ms; ++bl) {
if (!v[bl][tp].size() || R[bl][tp] < l || r < L[bl][tp]) continue;
if (l <= L[bl][tp] && R[bl][tp] <= r) {
lo = 0, hi = v[bl][tp].size() - 1, res = 0;
while (lo <= hi) {
mid = ((lo + hi) >> 1);
if (c[v[bl][tp][mid]] < k)
res = lo = mid + 1;
else
hi = mid - 1;
}
ret += v[bl][tp].size() - res;
}
else {
for (j = 0; j < v[bl][tp].size(); ++j) {
id = v[bl][tp][j];
if (c[id] < k) continue;
if (tp && a[id][1] <= r) ++ret;
if (!tp && l <= a[id][0]) ++ret;
}
}
}
return ret;
}
void up(ll x) {
while (x <= inf) {
G[x] += del;
x += (x & -x);
}
}
int gt(ll x) {
res = 0;
while (x > 0) {
res += G[x];
x -= (x & -x);
}
return res;
}
main () {
scanf("%d %d",&n, &t);
sq = sqrt(4*n);
ms = (n - 1 + sq - 1) / sq;
int lastans = 0, ans = 0, cnt = 0, u = 0, idx, ty, X, Y, Z, A, B, C;
for (int i = 0; i < n; ++i) {
if (!(i % sq)) Restart();
scanf("%d",&ty);
if (ty == 1) {
id = ++u, ++cnt;
scanf("%d %d",&a[u][0], &a[u][1]);
a[u][0] = (a[u][0] ^ (t * lastans));
a[u][1] = (a[u][1] ^ (t * lastans));
if (a[u][0] > a[u][1]) swap(a[u][0], a[u][1]);
c[u] = (a[u][1] - a[u][0] + 1);
tp = 0, p();
tp = 1, p();
del = 1, up(c[u]);
}
else
if (ty == 2) {
scanf("%d",&idx); --cnt, id = idx;
tp = 0, d();
tp = 1, d();
del = -1, up(c[id]);
}
else
if (ty == 3) {
scanf("%d %d %d",&A, &B, &C);
A = (A ^ (t * lastans));
B = (B ^ (t * lastans));
if (A > B) swap(A, B);
if (B - A + 1 < C) lastans = ans = 0;
else {
tp = 0, X = g(B - C + 2, 2e9, C);
tp = 1, Y = g(0, A + C - 2, C);
Z = gt(C - 1);
lastans = ans = cnt - (X + Y + Z);
}
printf("%d\n",ans);
}
}
}