| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1130892 | Gray | Segments (IZhO18_segments) | C++20 | 0 ms | 0 KiB |
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
const ll INF = 2e18;
const ll MOD = 1e9+7;
ll block_sz=2, upd_sz=2;
struct ranges{
struct block{
vector<ll> by_r, by_l;
};
vector<block> a;
vector<pair<ll, ll>> all;
vector<pair<ll, ll>> upd;
ll n, block_cnt;
void apply_upd(){
for (auto ch:upd) all.push_back(ch);
n=all.size(); upd.clear();
block_cnt = n/block_sz+(n%block_sz?1:0);
a.clear(); a.resize(block_cnt);
sort(all.begin(), all.end(), [](auto &op1, auto &op2){
return op1.ss-op1.ff<op2.ss-op2.ff;
});
for (ll i=0; i<n; i++){
a[i/block_sz].by_r.push_back(all[i].ss);
a[i/block_sz].by_l.push_back(all[i].ff);
}
for (ll i=0; i<block_cnt; i++){
sort(a[i].by_r.begin(), a[i].by_r.end());
sort(a[i].by_l.begin(), a[i].by_l.end());
}
}
void add(ll l, ll r){
upd.push_back({l, r});
if ((ll)upd.size()>upd_sz) apply_upd();
}
ll _query(ll l, ll r, ll k){
ll res=0;
if (!a.empty()){
ll ind = lower_bound(all.begin(), all.end(), mp(1, k), [](auto op1, auto op2){ return op1.ss-op1.ff<op2.ss-op2.ff;})-all.begin();
ll block_num = ind/block_sz;
res = n-ind;
for (ll i=block_num+1; i<block_cnt; i++){
res-=upper_bound(a[i].by_r.begin(), a[i].by_r.end(), l+k-2)-a[i].by_r.begin();
res-=a[i].by_l.end()-upper_bound(a[i].by_l.begin(), a[i].by_l.end(), r-k+1);
}
for (ll i=ind; i<min(n, (block_num+1)*block_sz); i++){
if (min(all[i].ss, r)-max(all[i].ff, l)+1<k) res--;
}
}
for (auto &ch:upd){
if (min(ch.ss, r)-max(ch.ff, l)+1>=k) res++;
}
return res;
}
ll query(ll l, ll r, ll k){
if (k) return _query(l, r, k);
else return upd.size()+n-query(l, r, 1);
}
};
void solve(){
ll n, t; cin >> n >> t;
ranges incl, excl;
ll lastans=0;
vector<pair<ll, ll>> ids;
while (n--){
ll type; cin >> type;
if (type==1){
ll a, b; cin >> a >> b;
ll l=a^(t*lastans), r = b^(t*lastans);
if (l>r) swap(l, r);
incl.add(l, r);
ids.push_back({l, r});
// cout << "Add: " << l << "-" << r << ln;
}else if (type==2){
ll id; cin >> id; id--;
excl.add(ids[id].ff, ids[id].ss);
}else{
ll a, b, k; cin >> a >> b >> k;
ll l=a^(t*lastans), r = b^(t*lastans);
if (l>r) swap(l, r);
// cout << l << "-" << r << ":";
lastans = incl.query(l, r, k)-excl.query(l, r, k);
// cout << incl.query(l, r, k) << "&" << excl.query(l, r, k) << " -> ";
cout << lastans << ln;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto start = chrono::high_resolution_clock::now();
ll t=1;
// cin >> t;
while (t--) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}