| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 633987 | fabijan_cikac | Segments (IZhO18_segments) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int, int>
#define ppp pair<int, pp>
#define F first
#define S second
#define pb push_back
const int N = 2 * 1e5 + 100;
const int BK = 300;
const int INF = 2 * 1e9 + 10;
int n, t; int buck = 0;
vector<ppp> a[BK]; int divs[N];
vector<ppp> b[BK];
vector<ppp> trash;
vector<ppp> trash2;
pp xy[N]; vector<int> L[2][BK];
vector<int> R[2][BK];
vector<ppp> st;
void move_trash(){
st.clear(); sort(trash.begin(), trash.end());
int cnt = 0;
for (int i = 0; i < BK; ++i){
if (a[i].empty()) break;
for (int j = 0; j < a[i].size(); ++j){
while (cnt < trash.size() && trash[cnt].F <= a[i][j].F){
st.pb(trash[cnt]); ++cnt;
}
st.pb(a[i][j]);
}
a[i].clear(); L[0][i].clear(); R[0][i].clear();
}
while (cnt < trash.size()){
st.pb(trash[cnt]); ++cnt;
}
trash.clear(); sort(st.begin(), st.end());
for (int i = 0; i < st.size(); ++i){
a[divs[i]].pb(st[i]);
L[0][divs[i]].pb(st[i].S.F);
R[0][divs[i]].pb(st[i].S.S);
}
for (int i = 0; i < BK; ++i){
if (L[0][i].empty()) return;
sort(L[0][i].begin(), L[0][i].end());
sort(R[0][i].begin(), R[0][i].end());
}
}
void move_trash2(){
st.clear(); sort(trash2.begin(), trash2.end());
int cnt = 0;
for (int i = 0; i < BK; ++i){
if (b[i].empty()) continue;
for (int j = 0; j < b[i].size(); ++j){
while (cnt < trash2.size() && trash2[cnt].F <= a[i][j].F){
st.pb(trash2[cnt]); ++cnt;
}
st.pb(b[i][j]);
}
b[i].clear(); L[1][i].clear(); R[1][i].clear();
}
while (cnt < trash2.size()){
st.pb(trash2[cnt]); ++cnt;
}
trash2.clear(); sort(st.begin(), st.end());
for (int i = 0; i < st.size(); ++i){
b[divs[i]].pb(st[i]);
L[1][divs[i]].pb(st[i].S.F);
R[1][divs[i]].pb(st[i].S.S);
}
for (int i = 0; i < BK; ++i){
if (L[1][i].empty()) return;
sort(L[1][i].begin(), L[1][i].end());
sort(R[1][i].begin(), R[1][i].end());
}
}
int bins_a(int l, int r, int k){
if (l == r) return l;
int mid = (l + r + 1) / 2;
if (a[mid].empty() || a[mid].back().F >= k) return bins_a(l, mid - 1, k);
return bins_a(mid, r, k);
}
int bins_b(int l, int r, int k){
if (l == r) return l;
int mid = (l + r + 1) / 2;
if (b[mid].empty() || b[mid].back().F >= k) return bins_b(l, mid - 1, k);
return bins_b(mid, r, k);
}
int bins_R(int x, int fl, int val, int l, int r){
if (l == r) return l;
int mid = (l + r + 1) / 2;
if (R[fl][x][mid] < val)
return bins_R(x, fl, val, mid, r);
return bins_R(x, fl, val, l, mid - 1);
}
int bins_L(int x, int fl, int val, int l, int r){
if (l == r) return l;
int mid = (l + r - 1) / 2;
if (L[fl][x][mid] > val)
return bins_L(x, fl, val, l, mid);
return bins_L(x, fl, val, mid + 1, r);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> t;
buck = n / BK + 1;
int lastans = 0; int cnt = 1;
int id = 1;
for (int i = 0; i < N; ++i) divs[i] = i / buck;
for (int i = 0; i < n; ++i){
int u; cin >> u;
if (cnt % buck == 0){
move_trash();
move_trash2();
}
if (u == 1){
int l, r; cin >> l >> r;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
if (l > r) swap(l, r);
trash.pb({r - l + 1, {l, r}});
sort(trash.begin(), trash.end());
xy[id] = {l, r}; ++cnt; ++id;
}
else if (u == 2){
int id; cin >> id;
trash2.pb({xy[id].S - xy[id].F + 1, xy[id]});
sort(trash2.begin(), trash2.end()); ++cnt;
}
else{
int l, r, k; cin >> l >> r >> k;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
if (l > r) swap(l, r);
if (k > r - l + 1){
cout << 0 << '\n'; lastans = 0; continue;
}
int ans = 0;
for (ppp x: trash){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) ++ans;
}
for (ppp x: trash2){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) --ans;
}
int pos1 = bins_a(0, BK - 1, k) + 1;
if (a[0].empty() || a[0].back().F >= k) pos1 = 0;
for (ppp x: a[pos1]){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) ++ans;
}
int pos2 = bins_b(0, BK - 1, k) + 1;
if (b[0].empty() || b[0].back().F >= k) pos2 = 0;
for (auto x: b[pos2]){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) --ans;
}
for (int i = pos1 + 1; i < BK; ++i){
if (a[i].empty()) break;
int num = a[i].size();
if (L[0][i].back() > r - k + 1)
num -= (L[0][i].size() - bins_L(i, 0, r - k + 1, 0, L[0][i].size() - 1));
if (R[0][i][0] < l + k - 1)
num -= (bins_R(i, 0, l + k - 1, 0, R[0][i].size() - 1) + 1);
ans += num;
}
for (int i = pos2 + 1; i < BK; ++i){
if (b[i].empty()) break;
int num = b[i].size();
if (L[1][i].back() > r - k + 1)
num -= (L[1][i].size() - bins_L(i, 1, r - k + 1, 0, L[1][i].size() - 1));
if (R[1][i][0] < l + k - 1)
num -= (bins_R(i, 1, l + k - 1, 0, R[1][i].size() - 1) + 1);
ans -= num;
}
lastans = ans; cout << ans << '\n';
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int, int>
#define ppp pair<int, pp>
#define F first
#define S second
#define pb push_back
const int N = 2 * 1e5 + 100;
const int BK = 300;
const int INF = 2 * 1e9 + 10;
int n, t; int buck = 0;
vector<ppp> a[BK]; int divs[N];
vector<ppp> b[BK];
vector<ppp> trash;
vector<ppp> trash2;
pp xy[N]; vector<int> L[2][BK];
vector<int> R[2][BK];
vector<ppp> st;
void move_trash(){
st.clear(); sort(trash.begin(), trash.end());
int cnt = 0;
for (int i = 0; i < BK; ++i){
if (a[i].empty()) break;
for (int j = 0; j < a[i].size(); ++j){
while (cnt < trash.size() && trash[cnt].F <= a[i][j].F){
st.pb(trash[cnt]); ++cnt;
}
st.pb(a[i][j]);
}
a[i].clear(); L[0][i].clear(); R[0][i].clear();
}
while (cnt < trash.size()){
st.pb(trash[cnt]); ++cnt;
}
trash.clear(); sort(st.begin(), st.end());
for (int i = 0; i < st.size(); ++i){
a[divs[i]].pb(st[i]);
L[0][divs[i]].pb(st[i].S.F);
R[0][divs[i]].pb(st[i].S.S);
}
for (int i = 0; i < BK; ++i){
if (L[0][i].empty()) return;
sort(L[0][i].begin(), L[0][i].end());
sort(R[0][i].begin(), R[0][i].end());
}
}
void move_trash2(){
st.clear(); sort(trash2.begin(), trash2.end());
int cnt = 0;
for (int i = 0; i < BK; ++i){
if (b[i].empty()) continue;
for (int j = 0; j < b[i].size(); ++j){
while (cnt < trash2.size() && trash2[cnt].F <= a[i][j].F){
st.pb(trash2[cnt]); ++cnt;
}
st.pb(b[i][j]);
}
b[i].clear(); L[1][i].clear(); R[1][i].clear();
}
while (cnt < trash2.size()){
st.pb(trash2[cnt]); ++cnt;
}
trash2.clear(); sort(st.begin(), st.end());
for (int i = 0; i < st.size(); ++i){
b[divs[i]].pb(st[i]);
L[1][divs[i]].pb(st[i].S.F);
R[1][divs[i]].pb(st[i].S.S);
}
for (int i = 0; i < BK; ++i){
if (L[1][i].empty()) return;
sort(L[1][i].begin(), L[1][i].end());
sort(R[1][i].begin(), R[1][i].end());
}
}
int bins_a(int l, int r, int k){
if (l == r) return l;
int mid = (l + r + 1) / 2;
if (a[mid].empty() || a[mid].back().F >= k) return bins_a(l, mid - 1, k);
return bins_a(mid, r, k);
}
int bins_b(int l, int r, int k){
if (l == r) return l;
int mid = (l + r + 1) / 2;
if (b[mid].empty() || b[mid].back().F >= k) return bins_b(l, mid - 1, k);
return bins_b(mid, r, k);
}
int bins_R(int x, int fl, int val, int l, int r){
if (l == r) return l;
int mid = (l + r + 1) / 2;
if (R[fl][x][mid] < val)
return bins_R(x, fl, val, mid, r);
return bins_R(x, fl, val, l, mid - 1);
}
int bins_L(int x, int fl, int val, int l, int r){
if (l == r) return l;
int mid = (l + r - 1) / 2;
if (L[fl][x][mid] > val)
return bins_L(x, fl, val, l, mid);
return bins_L(x, fl, val, mid + 1, r);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> t;
buck = n / BK + 1;
int lastans = 0; int cnt = 1;
int id = 1;
for (int i = 0; i < N; ++i) divs[i] = i / buck;
for (int i = 0; i < n; ++i){
int u; cin >> u;
if (cnt % buck == 0){
move_trash();
move_trash2();
}
if (u == 1){
int l, r; cin >> l >> r;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
if (l > r) swap(l, r);
trash.pb({r - l + 1, {l, r}});
sort(trash.begin(), trash.end());
xy[id] = {l, r}; ++cnt; ++id;
}
else if (u == 2){
int id; cin >> id;
trash2.pb({xy[id].S - xy[id].F + 1, xy[id]});
sort(trash2.begin(), trash2.end()); ++cnt;
}
else{
int l, r, k; cin >> l >> r >> k;
l = (l ^ (t * lastans));
r = (r ^ (t * lastans));
if (l > r) swap(l, r);
if (k > r - l + 1){
cout << 0 << '\n'; lastans = 0; continue;
}
int ans = 0;
for (ppp x: trash){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) ++ans;
}
for (ppp x: trash2){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) --ans;
}
int pos1 = bins_a(0, BK - 1, k) + 1;
if (a[0].empty() || a[0].back().F >= k) pos1 = 0;
for (ppp x: a[pos1]){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) ++ans;
}
int pos2 = bins_b(0, BK - 1, k) + 1;
if (b[0].empty() || b[0].back().F >= k) pos2 = 0;
for (auto x: b[pos2]){
if (min(r, x.S.S) - max(x.S.F, l) + 1 >= k) --ans;
}
for (int i = pos1 + 1; i < BK; ++i){
if (a[i].empty()) break;
int num = a[i].size();
if (L[0][i].back() > r - k + 1)
num -= (L[0][i].size() - bins_L(i, 0, r - k + 1, 0, L[0][i].size() - 1));
if (R[0][i][0] < l + k - 1)
num -= (bins_R(i, 0, l + k - 1, 0, R[0][i].size() - 1) + 1);
ans += num;
}
for (int i = pos2 + 1; i < BK; ++i){
if (b[i].empty()) break;
int num = b[i].size();
if (L[1][i].back() > r - k + 1)
num -= (L[1][i].size() - bins_L(i, 1, r - k + 1, 0, L[1][i].size() - 1));
if (R[1][i][0] < l + k - 1)
num -= (bins_R(i, 1, l + k - 1, 0, R[1][i].size() - 1) + 1);
ans -= num;
}
lastans = ans; cout << ans << '\n';
}
}
return 0;
}