#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int K=1900;
multiset<pair<int,pii>>ms;
vector<pii>bl[120],br[120];
int mn[120]{0},mx[120]{0};
vector<pair<int,pii>>cur,upd;
void build(){
cur.clear();
for(auto it : ms)cur.pb({it.s.s-it.s.f+1,{it.s.f,it.s.s}});
for(int i=0;i<120;i++)bl[i].clear(),br[i].clear(),mx[i]=0,mn[i]=2e9+5;
sort(all(cur));
for(int i=0;i<cur.size();i++){
bl[i/K].pb({cur[i].s.f,cur[i].s.s});
br[i/K].pb({cur[i].s.s,cur[i].s.f});
mx[i/K]=max(mx[i/K],cur[i].f);
mn[i/K]=min(mn[i/K],cur[i].f);
}for(int i=0;i<120;i++)sort(all(bl[i])),sort(all(br[i]));
upd.clear();
}
int qr(int k,int l,int r,int ans=0){
for(int i=0;i<120;i++){
if(mx[i]<k)continue;
if(mn[i]>=k){ans+=bl[i].size();continue;}
for(auto it : bl[i]){
if(it.s-it.f+1>=k)ans++;
}
}
for(int i=0;i<120;i++){
if(mx[i]<k)continue;
if(mn[i]>=k){
int l=0,r=(int)bl[i].size();
while(l<r){
int m=(l+r)>>1;
if(bl[i][m].f>=r-k+1)r=m;
else l=m+1;
}ans-=(int)bl[i].size()-l;continue;
}
for(auto it : bl[i]){
if(it.s-it.f+1>=k&&it.f>=r-k+1)ans--;
}
}
for(int i=0;i<120;i++){
if(mx[i]<k)continue;
if(mn[i]>=k){
int l=-1,r=(int)br[i].size()-1;
while(l<r){
int m=(l+r+1)>>1;
if(br[i][m].f<=l-k+1)l=m;
else r=m-1;
}ans-=(l+1);continue;
}
for(auto it : br[i]){
if(it.f-it.s+1>=k&&it.f<=l-k+1)ans--;
}
}
for(auto it : upd){
if(min(r,it.s.s)-max(l,it.s.f)+1>=k)ans+=it.f;
}return ans;
}int id=1;
pii seg[200006];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,t;cin>>n>>t;ll res=0;
for(int i=0;i<n;i++){
if(i%K==0)build();
int o;cin>>o;
if(o==1){
int a,b;cin>>a>>b;
a=(a^(t*res)),b=(b^(t*res));
if(a>b)swap(a,b);seg[id]={a,b};
ms.insert({id,{a,b}});id++;
upd.pb({1,{a,b}});
}
if(o==2){
int c;cin>>c;
ms.erase(ms.lower_bound({c,{0,0}}));
upd.pb({-1,{seg[c].f,seg[c].s}});
}
if(o==3){
int a,b,k;cin>>a>>b>>k;
a=(a^(t*res)),b=(b^(t*res));
if(a>b)swap(a,b);
if(b-a+1<k)res=0;
else res=qr(k,a,b);
cout<<res<<'\n';
}
}
}
Compilation message
segments.cpp: In function 'void build()':
segments.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<cur.size();i++){
| ~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:81:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
81 | if(a>b)swap(a,b);seg[id]={a,b};
| ^~
segments.cpp:81:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
81 | if(a>b)swap(a,b);seg[id]={a,b};
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1042 ms |
8396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
2640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
