///mnogo trqbva da se vnimava s lower/upperbound queryta v pair
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+3;
const int crit = 2000;
int i,j,p,q,n,m,k,L,R,A,B,lans,id,lb[maxn],rb[maxn],block[maxn],minlen[maxn],t,curlen;
vector < pair <int,int> > cur,all;
vector < pair <int,int> > levi[100],desni[100];//n/crit
int removed[maxn];
void insert(int l,int r,int nom)
{
cur.push_back({r-l+1,nom});
if(cur.size()==crit)
{
vector <pair <int,int>> neww;
for(i=0; i<=all.size()/crit+2; i++)
levi[i].clear(),desni[i].clear(),minlen[i] = -1;
for(auto i:cur)
neww.push_back(i);
for(auto i:all)
neww.push_back(i);
cur.clear();
all.clear();
for(auto i:neww)
{
if(!removed[i.second])
all.push_back(i);
}
///build the structure
sort(all.rbegin(),all.rend());
int bl = 0;
int br = 0;
int Min = INT_MAX;
for(auto i:all)
{
levi[bl].push_back({lb[i.second],i.second});
desni[bl].push_back({rb[i.second],i.second});
Min = min(Min,i.first);
block[i.second] = bl;
br++;
if(br==crit)
{
minlen[bl] = Min;
Min = INT_MAX;
bl++;
br = 0;
}
}
for(i=0; i<=all.size()/crit+2; i++)
{
if(levi[i].empty())break;
sort(levi[i].begin(),levi[i].end());
sort(desni[i].begin(),desni[i].end());
}
}
}
void remove(int id)
{
removed[id] = true;
if(block[id]==-1)
{
vector < pair <int,int> > newws;
for(auto i:cur)
if(i.second!=id)newws.push_back(i);
cur = newws;
return ;
}
p = block[id];
vector < pair <int,int> > newws;
for(auto i:levi[p])
if(i.second!=id)newws.push_back(i);
levi[p] = newws;
newws.clear();
for(auto i:desni[p])
if(i.second!=id)newws.push_back(i);
desni[p] = newws;
block[id] = -1;
}
int solve(int l,int r,int k)
{
int ans = 0;
for(auto i:cur)
{
//cout<<lb[i.second]<<" "<<rb[i.second]<<" "<<l<<" "<<r<<" "<<k<<endl;
if(min(rb[i.second],r)-max(lb[i.second],l)+1>=k)
ans++;
}
for(i=0; i<=all.size()/crit+1; i++)
{
if(minlen[i]==-1)break;
if(minlen[i]<k)
{
///iterative check
j = i;
for(auto i:levi[j])
{
if(removed[i.second])
continue;
if(min(rb[i.second],r)-max(lb[i.second],l)+1>=k)
ans++;
}
break;
}
ans+=levi[i].size();
p = 0;
///indexed from 0
p += upper_bound(desni[i].begin(),desni[i].end(), make_pair(l+k-2,10000000))-desni[i].begin();
p += levi[i].size()-(lower_bound(levi[i].begin(),levi[i].end(), make_pair(r-k+2,-1))-levi[i].begin());
ans-=p;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>t;
for(i=0; i<=n; i++)
block[i] = -1,minlen[i] = -1;
lans = 0;
while(n--)
{
int type;
cin>>type;
if(type==1)
{
cin>>A>>B;
L = A^(t*lans);
R = B^(t*lans);
if(L>R)swap(L,R);
curlen++;
lb[curlen] = L;
rb[curlen] = R;
insert(L,R,curlen);
}
else if(type==2)
{
cin>>id;
remove(id);
}
else
{
cin>>A>>B>>k;
L = A^(t*lans);
R = B^(t*lans);
if(L>R)swap(L,R);
lans = solve(L,R,k);
cout<<lans<<endl;
}
}
return 0;
}
/**
6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1
6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/
Compilation message
segments.cpp: In function 'void insert(int, int, int)':
segments.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(i=0; i<=all.size()/crit+2; i++)
| ~^~~~~~~~~~~~~~~~~~~
segments.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(i=0; i<=all.size()/crit+2; i++)
| ~^~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int solve(int, int, int)':
segments.cpp:94:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(i=0; i<=all.size()/crit+1; i++)
| ~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
4 ms |
2548 KB |
Output is correct |
4 |
Correct |
4 ms |
2524 KB |
Output is correct |
5 |
Correct |
7 ms |
2652 KB |
Output is correct |
6 |
Correct |
12 ms |
2652 KB |
Output is correct |
7 |
Correct |
8 ms |
2396 KB |
Output is correct |
8 |
Correct |
10 ms |
2652 KB |
Output is correct |
9 |
Correct |
11 ms |
2652 KB |
Output is correct |
10 |
Correct |
5 ms |
2652 KB |
Output is correct |
11 |
Correct |
17 ms |
2660 KB |
Output is correct |
12 |
Correct |
17 ms |
2904 KB |
Output is correct |
13 |
Correct |
5 ms |
2652 KB |
Output is correct |
14 |
Correct |
11 ms |
2652 KB |
Output is correct |
15 |
Correct |
3 ms |
2396 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
10 ms |
2396 KB |
Output is correct |
18 |
Incorrect |
7 ms |
2652 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
813 ms |
4904 KB |
Output is correct |
2 |
Correct |
793 ms |
4684 KB |
Output is correct |
3 |
Correct |
772 ms |
4772 KB |
Output is correct |
4 |
Correct |
696 ms |
5148 KB |
Output is correct |
5 |
Correct |
445 ms |
7084 KB |
Output is correct |
6 |
Correct |
453 ms |
7188 KB |
Output is correct |
7 |
Correct |
789 ms |
4772 KB |
Output is correct |
8 |
Correct |
761 ms |
4828 KB |
Output is correct |
9 |
Correct |
765 ms |
4696 KB |
Output is correct |
10 |
Correct |
780 ms |
3780 KB |
Output is correct |
11 |
Correct |
748 ms |
3892 KB |
Output is correct |
12 |
Correct |
585 ms |
6200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
89 ms |
2900 KB |
Output is correct |
2 |
Correct |
69 ms |
2852 KB |
Output is correct |
3 |
Correct |
125 ms |
3032 KB |
Output is correct |
4 |
Correct |
71 ms |
2896 KB |
Output is correct |
5 |
Correct |
438 ms |
6224 KB |
Output is correct |
6 |
Correct |
385 ms |
5320 KB |
Output is correct |
7 |
Correct |
443 ms |
5528 KB |
Output is correct |
8 |
Correct |
432 ms |
7080 KB |
Output is correct |
9 |
Incorrect |
423 ms |
7304 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
68 ms |
2848 KB |
Output is correct |
2 |
Correct |
75 ms |
2904 KB |
Output is correct |
3 |
Correct |
71 ms |
2912 KB |
Output is correct |
4 |
Correct |
79 ms |
2896 KB |
Output is correct |
5 |
Correct |
570 ms |
6596 KB |
Output is correct |
6 |
Correct |
860 ms |
3828 KB |
Output is correct |
7 |
Correct |
559 ms |
6552 KB |
Output is correct |
8 |
Correct |
673 ms |
3500 KB |
Output is correct |
9 |
Incorrect |
499 ms |
4804 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
4 ms |
2548 KB |
Output is correct |
4 |
Correct |
4 ms |
2524 KB |
Output is correct |
5 |
Correct |
7 ms |
2652 KB |
Output is correct |
6 |
Correct |
12 ms |
2652 KB |
Output is correct |
7 |
Correct |
8 ms |
2396 KB |
Output is correct |
8 |
Correct |
10 ms |
2652 KB |
Output is correct |
9 |
Correct |
11 ms |
2652 KB |
Output is correct |
10 |
Correct |
5 ms |
2652 KB |
Output is correct |
11 |
Correct |
17 ms |
2660 KB |
Output is correct |
12 |
Correct |
17 ms |
2904 KB |
Output is correct |
13 |
Correct |
5 ms |
2652 KB |
Output is correct |
14 |
Correct |
11 ms |
2652 KB |
Output is correct |
15 |
Correct |
3 ms |
2396 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
10 ms |
2396 KB |
Output is correct |
18 |
Incorrect |
7 ms |
2652 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
4 ms |
2548 KB |
Output is correct |
4 |
Correct |
4 ms |
2524 KB |
Output is correct |
5 |
Correct |
7 ms |
2652 KB |
Output is correct |
6 |
Correct |
12 ms |
2652 KB |
Output is correct |
7 |
Correct |
8 ms |
2396 KB |
Output is correct |
8 |
Correct |
10 ms |
2652 KB |
Output is correct |
9 |
Correct |
11 ms |
2652 KB |
Output is correct |
10 |
Correct |
5 ms |
2652 KB |
Output is correct |
11 |
Correct |
17 ms |
2660 KB |
Output is correct |
12 |
Correct |
17 ms |
2904 KB |
Output is correct |
13 |
Correct |
5 ms |
2652 KB |
Output is correct |
14 |
Correct |
11 ms |
2652 KB |
Output is correct |
15 |
Correct |
3 ms |
2396 KB |
Output is correct |
16 |
Correct |
4 ms |
2396 KB |
Output is correct |
17 |
Correct |
10 ms |
2396 KB |
Output is correct |
18 |
Incorrect |
7 ms |
2652 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |