Submission #898491

#	Time	Username	Problem	Language	Result	Execution time	Memory
898491		Denkata	Segments (IZhO18_segments)	C++17	7 / 100	369 ms	65536 KiB

segments

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+3;
const int crit = 5000;
int i,j,p,q,n,m,k,a[maxn],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[200],desni[200];//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; 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();

        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 = 1e7;
        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 = 1e7;
                bl++;
                br = 0;
            }
        }

        for(i=0; i<all.size()/crit; i++)
        {
            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)
        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;
}
int solve(int l,int r,int k)
{
    int ans = 0;
    for(auto i:cur)
    {
        if(removed[i.second])
            continue;
        //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; i++)
    {
        if(levi[i].empty())continue;///could be optimized
        if(minlen[i]<k)
        {
            ///iterative check
            for(auto i:levi[i])
            {
                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 += lower_bound(desni[i].begin(),desni[i].end(), make_pair(l+k-1,-1))-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;
    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 (stderr)

segments.cpp: In function 'void insert(int, int, int)':
segments.cpp:16: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]
   16 |         for(i=0; i<all.size()/crit; i++)
      |                  ~^~~~~~~~~~~~~~~~
segments.cpp:51: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]
   51 |         for(i=0; i<all.size()/crit; i++)
      |                  ~^~~~~~~~~~~~~~~~
segments.cpp: In function 'int solve(int, int, int)':
segments.cpp:86: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]
   86 |     for(i=0; i<all.size()/crit; i++)
      |              ~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25