Submission #1025299

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1025299	2024-07-16T19:27:30 Z	Vanio	Segments (IZhO18_segments)	C++17	Compilation error	0 ms	0 KB

segments

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("avx2")

#include<bits/stdc++.h>
using namespace std;

struct segment{
    int l,r;
};
segment seg[200001],tseg[200001];
bool fff(segment p, segment q){
    return p.r-p.l>q.r-q.l;
}

struct block{
    int mi=INT_MAX,ma=-1;
    vector<int> vl,vr;
};
block b[501];

struct query{
    int qt,id,l,r,k;
};
query qs[200001];

int n,segbr,t,nextSegmentId,lastans,bsz,bbr,qbStart=1;
set<int> segmentIds;

void buildStructure(){
    int i=1;
    segbr=segmentIds.size();
    for(int it : segmentIds){
        tseg[i]=seg[it];
        ++i;
    }

    sort(tseg+1,tseg+1+segbr,fff);
    bsz=sqrt(segbr)+1;
    bbr=segbr/bsz;
    if(segbr%bsz>0) bbr++;
    int bindx=0;
    for(i=1;i<=segbr;++i){
        if(i%bsz==1) bindx++;
        b[bindx].mi=INT_MAX;
        b[bindx].ma=-1;
        b[bindx].vl.clear();
        b[bindx].vr.clear();
    }
    bindx=0;
    for(i=1;i<=segbr;++i){
        if(i%bsz==1) bindx++;
        //cout<<bindx<<" "<<seg[i].l<<" "<<seg[i].r<<'\n';
        b[bindx].mi=min(b[bindx].mi,tseg[i].r-tseg[i].l+1);
        b[bindx].ma=max(b[bindx].ma,tseg[i].r-tseg[i].l+1);
        b[bindx].vl.push_back(tseg[i].l);
        b[bindx].vr.push_back(tseg[i].r);
    }

    for(i=1;i<=bbr;++i){
        sort(b[i].vl.begin(),b[i].vl.end());
        sort(b[i].vr.begin(),b[i].vr.end());
    }
}

void handleQt1(int k){
    nextSegmentId++;
    qs[k].qt=1;
    qs[k].id=nextSegmentId;
    cin>>seg[nextSegmentId].l>>seg[nextSegmentId].r;
    seg[nextSegmentId].l^=lastans*t;
    seg[nextSegmentId].r^=lastans*t;
    if(seg[nextSegmentId].l>seg[nextSegmentId].r) swap(seg[nextSegmentId].l,seg[nextSegmentId].r);
    segmentIds.insert(nextSegmentId);
}

void handleQt2(int k){
    qs[k].qt=2;
    cin>>qs[k].id;
    segmentIds.erase(qs[k].id);
}

void handleQt3(int ti){
    int l,r,k,ans=0,j,i;
    cin>>l>>r>>k;

    ans=segbr;
    l^=lastans*t;
    r^=lastans*t;
    if(l>r) swap(l,r);

    //cout<<"qt3 "<<l<<" "<<r<<" "<<k<<endl;
    for(i=1;i<=bbr;++i){
        if(b[i].mi>=k){
            auto it = lower_bound(b[i].vl.begin(),b[i].vl.end(),r-k+2);
            //cout<<"1 "<<b[i].vl.end()-it<<endl;
            ans-=b[i].vl.end()-it;
            auto it2 = upper_bound(b[i].vr.begin(),b[i].vr.end(),l+k-2);
            //cout<<"1 "<<it2-b[i].vr.begin()<<endl;
            ans-=it2-b[i].vr.begin();
        }
        else if(b[i].mi<k && k<=b[i].ma){
            for(j=(i-1)*bsz+1;j<=i*bsz && j<=segbr;++j){
                if(tseg[j].r-tseg[j].l+1<k || tseg[j].l>=r-k+2 || tseg[j].r<=l+k-2){ans--; /*cout<<"2 "<<j<<" "<<seg[j].l<<" "<<seg[j].r<<endl;*/}
            }
        }
        else{
            ans-=segbr-bsz*(i-1);
            //cout<<segbr-bsz*(i-1)<<endl;
            break;
        }
    }

    int segId;
    for(i=ti-1;i>=qbStart;--i){
        if(qs[i].qt==1){
            segId=qs[i].id;
            if(min(r,seg[segId].r)-max(l,seg[segId].l)+1>=k) ans++;
        }
        if(qs[i].qt==2){
            segId=qs[i].id;
            if(min(r,seg[segId].r)-max(l,seg[segId].l)+1>=k) ans--;
        }
    }

    lastans=ans;
    cout<<ans<<'\n';
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int i,qt,l,r,id,k,f=0,qbsz;
cin>>n>>t;
qbsz=max(sqrt(n)-1,1);

for(i=1;i<=n;++i){
    if(i%qbsz==1){
        buildStructure();
        qbStart=i;
        //cout<<"new query block "<<i<<" "<<segbr<<endl;
    }

    cin>>qt;
    if(qt==1) handleQt1(i);
    if(qt==2) handleQt2(i);
    if(qt==3) handleQt3(i);
}

return 0;
}
/*
6 1
1 1 2
1 3 8
1 5 8
1 2 4
1 8 10
3 3 7 2

25 1
1 97 61
1 21 92
1 57 10
1 77 46
1 60 54
1 34 35
1 7 66
1 71 61
1 64 19
1 22 80
1 81 39
1 57 52
1 9 4
1 17 28
1 16 51
1 67 2
1 25 51
1 42 83
1 61 65
1 37 45
3 31 34 2
3 36 37 1
3 44 62 8
3 65 67 3
3 84 92 6

8   8
11  11
16  11
3   6
2   2
*/

Compilation message

segments.cpp:3:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("avx2")
      |                            ^
segments.cpp:12:30: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   12 | bool fff(segment p, segment q){
      |                              ^
segments.cpp:30:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   30 | void buildStructure(){
      |                     ^
segments.cpp:66:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   66 | void handleQt1(int k){
      |                     ^
segments.cpp:77:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   77 | void handleQt2(int k){
      |                     ^
segments.cpp:83:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   83 | void handleQt3(int ti){
      |                      ^
segments.cpp:130:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  130 | int main()
      |          ^
segments.cpp: In function 'int main()':
segments.cpp:138:21: error: no matching function for call to 'max(__gnu_cxx::__enable_if<true, double>::__type, int)'
  138 | qbsz=max(sqrt(n)-1,1);
      |                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from segments.cpp:5:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
segments.cpp:138:21: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'int')
  138 | qbsz=max(sqrt(n)-1,1);
      |                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from segments.cpp:5:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
segments.cpp:138:21: note:   deduced conflicting types for parameter 'const _Tp' ('double' and 'int')
  138 | qbsz=max(sqrt(n)-1,1);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from segments.cpp:5:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
segments.cpp:138:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
  138 | qbsz=max(sqrt(n)-1,1);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from segments.cpp:5:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
segments.cpp:138:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'double'
  138 | qbsz=max(sqrt(n)-1,1);
      |                     ^
segments.cpp:136:10: warning: unused variable 'l' [-Wunused-variable]
  136 | int i,qt,l,r,id,k,f=0,qbsz;
      |          ^
segments.cpp:136:12: warning: unused variable 'r' [-Wunused-variable]
  136 | int i,qt,l,r,id,k,f=0,qbsz;
      |            ^
segments.cpp:136:14: warning: unused variable 'id' [-Wunused-variable]
  136 | int i,qt,l,r,id,k,f=0,qbsz;
      |              ^~
segments.cpp:136:17: warning: unused variable 'k' [-Wunused-variable]
  136 | int i,qt,l,r,id,k,f=0,qbsz;
      |                 ^
segments.cpp:136:19: warning: unused variable 'f' [-Wunused-variable]
  136 | int i,qt,l,r,id,k,f=0,qbsz;
      |                   ^