이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5+1, MAGIC = 1200;
class TaskD {
int n, T, id[N], last[N], blk[N];
bool valid[N];
pair<int,int> segs[N];
vector<pair<int,int> > fl, fr;
vector<vector<int> > tl, tr;
int get_r(int l, int r, int targ_r) {
int ret = 0;
for(l += fr.size(), r += fr.size() + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) {
auto it = lower_bound(tr[l].begin(), tr[l].end(), targ_r);
ret += it - tr[l].begin();
// cout << "get_r " << it - tr[l].begin() << ' ' << *(--it) << endl;
// for(int x: tr[l]) cout << x << ' ';
// cout << endl;
++l;
}
if(r & 1) {
--r;
auto it = lower_bound(tr[r].begin(), tr[r].end(), targ_r);
ret += it - tr[r].begin();
// cout << "get_r " << it - tr[r].begin() << ' ' << *(--it) << endl;
// for(int x: tr[r]) cout << x << ' ';
// cout << endl;
}
}
return ret;
}
int get_l(int l, int r, int targ_l) {
int ret = 0;
for(l += fl.size(), r += fl.size() + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) {
auto it = upper_bound(tl[l].begin(), tl[l].end(), targ_l);
ret += tl[l].end() - it;
++l;
}
if(r & 1) {
--r;
auto it = upper_bound(tl[r].begin(), tl[r].end(), targ_l);
ret += tl[r].end() - it;
}
}
return ret;
}
void build() {
tl.clear();
tr.clear();
tl.resize(2 * fl.size());
tr.resize(2 * fr.size());
sort(fl.begin(), fl.end());
sort(fr.begin(), fr.end());
for(int i = 0; i < fl.size(); i++) tl[fl.size() + i] = {fl[i].second};
for(int i = 0; i < fr.size(); i++) tr[fr.size() + i] = {fr[i].second};
for(int i = fl.size()-1; i >= 1; i--) {
merge(tl[i << 1].begin(), tl[i << 1].end(), tl[i << 1 | 1].begin(), tl[i << 1 | 1].end(),
back_inserter(tl[i]));
// cout << i << ' ';
// for(int x: tl[i]) cout << x << ' ';
// cout << endl;
}
for(int i = fr.size()-1; i >= 1; i--) {
merge(tr[i << 1].begin(), tr[i << 1].end(), tr[i << 1 | 1].begin(), tr[i << 1 | 1].end(),
back_inserter(tr[i]));
}
}
public:
void solve(istream &cin, ostream &cout) {
cin >> n >> T;
int lastans = 0, tick = 0, alive = 0;
for(int i = 0; i < n; i++) {
segs[i] = {-1, -1};
blk[i] = i / MAGIC;
}
for(int i = 0, inst; i < n; i++) {
if(i % MAGIC == 0) {
fl.clear();
fr.clear();
for(int j = 0; j < i; j++) {
if(!valid[id[j]]) continue;
int len = segs[id[j]].second - segs[id[j]].first + 1;
fl.emplace_back(len, segs[id[j]].first);
fr.emplace_back(len, segs[id[j]].second);
}
build();
}
cin >> inst;
if(inst == 1) {
int l, r;
cin >> l >> r;
l ^= T * lastans;
r ^= T * lastans;
if(l > r) swap(l, r);
id[i] = ++tick;
valid[id[i]] = true;
last[id[i]] = i;
segs[id[i]] = {l, r};
++alive;
} else if(inst == 2) {
int x;
cin >> x;
id[i] = x;
valid[id[i]] = false;
--alive;
} else {
int l, r, k;
cin >> l >> r >> k;
l ^= T * lastans;
r ^= T * lastans;
if(l > r) swap(l, r);
lastans = 0;
if(r-l+1 < k) {
cout << lastans << '\n';
continue;
}
// outside block -> three cases
int idx = lower_bound(fl.begin(), fl.end(), make_pair(k, 0)) - fl.begin();
lastans += idx; // len < k
lastans += get_l(idx, fl.size() - 1, r - k + 1); // l[j] > r[i] - k[i] + 1 and len >= k
lastans += get_r(idx, fr.size() - 1, l + k - 1); // r[j] < l[i] + k[i] - 1 and len >= k
// within same block
for(int j = i-1; j >= 0 && blk[j] == blk[i]; j--) {
if(valid[id[j]]) {
lastans += min(segs[id[j]].second, r) - max(segs[id[j]].first, l) + 1 < k;
} else if(segs[id[j]].first != -1 && blk[last[id[j]]] < blk[i]) {
lastans -= min(segs[id[j]].second, r) - max(segs[id[j]].first, l) + 1 < k;
}
}
lastans = alive - lastans;
cout << lastans << '\n';
}
}
}
};
class Solver {
public:
void solve(std::istream& in, std::ostream& out) {
TaskD *obj = new TaskD();
obj->solve(in, out);
delete obj;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solver solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
segments.cpp: In member function 'void TaskD::build()':
segments.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < fl.size(); i++) tl[fl.size() + i] = {fl[i].second};
~~^~~~~~~~~~~
segments.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < fr.size(); i++) tr[fr.size() + i] = {fr[i].second};
~~^~~~~~~~~~~
# | 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... |