이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long llint;
const int maxn = 2e5+10;
const int block = 600;
int n, t;
int cnt = 0;
vector< int > lef[maxn], rig[maxn];
int L[maxn], R[maxn];
int bio[maxn];
vector< pair<int, int> > v;
int inds[maxn];
int ptr;
bool cmp(int x, int y) {
return R[x] - L[x] < R[y] - L[y];
}
inline int inter(int ax, int ay, int bx, int by) {
return min(ay, by) - max(ax, bx) + 1;
}
int main() {
scanf("%d%d", &n, &t);
int lastans = 0;
while (n--) {
int type;
scanf("%d", &type);
if (type == 1) {
int l, r;
scanf("%d%d", &l, &r);
l = l ^ (t * lastans);
r = r ^ (t * lastans);
if (l > r) swap(l, r);
//printf("adding: %d %d\n", l, r);
++cnt;
v.push_back({cnt, 1});
L[cnt] = l, R[cnt] = r;
} else if (type == 2) {
int x;
scanf("%d", &x);
v.push_back({x, -1});
} else {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
l = l ^ (t * lastans);
r = r ^ (t * lastans);
if (l > r) swap(l, r);
//printf("query: %d %d\n", l, r);
lastans = 0;
for (int i = 0; i < ptr; i += block) {
int tr = i / block;
int las = min(ptr, i + block) - 1;
/*printf("block: ");
for (int j = 0; j < block; j++) {
if (i + j >= inds.size()) break;
printf("(%d %d) ", L[inds[i + j]], R[inds[i + j]]);
}
printf("\n");*/
if (R[inds[las]] - L[inds[las]] + 1 < k) continue;
if (R[inds[i]] - L[inds[i]] + 1 >= k) {
lastans += las - i + 1;
int ind = lower_bound(rig[tr].begin(), rig[tr].end(), l + k - 1) - rig[tr].begin();
//printf("removing: %d\n", ind);
lastans -= ind;
ind = upper_bound(lef[tr].begin(), lef[tr].end(), r - k + 1) - lef[tr].begin();
lastans -= lef[tr].size() - ind;
//printf("removing: %d\n", lef[tr].size() - ind);
} else {
for (int j = 0; j < block; j++) {
if (i + j >= ptr) break;
lastans += (inter(l, r, L[inds[i + j]], R[inds[i + j]]) >= k);
}
}
}
for (auto &iter : v) {
int ind = iter.X;
int cost = iter.Y;
if (inter(l, r, L[ind], R[ind]) >= k) lastans += cost;
}
printf("%d\n", lastans);
}
if (n % block == 0) {
for (int i = 0; i <= ptr / block; i++) {
lef[i].clear();
rig[i].clear();
}
for (auto &iter : v) {
bio[iter.X] += iter.Y;
}
v.clear();
ptr = 0;
for (int i = 1; i <= cnt; i++) {
if (bio[i]) inds[ptr++] = i;
}
sort(inds, inds + ptr, cmp);
for (int i = 0; i < ptr; i++) {
int tr = i / block;
lef[tr].push_back(L[inds[i]]);
rig[tr].push_back(R[inds[i]]);
}
for (int i = 0; i <= ptr / block; i++) {
sort(lef[i].begin(), lef[i].end());
sort(rig[i].begin(), rig[i].end());
}
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp: In function 'int main()':
segments.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d%d", &n, &t);
| ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d", &type);
| ~~~~~^~~~~~~~~~~~~
segments.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
segments.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
segments.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |