oj.uz

답안 #1025312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025312 2024-07-16T19:44:04 Z Vanio Segments (IZhO18_segments) C++17
15 / 100
 2071 ms 8392 KB 
#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;
vector<int> segmentIds;
bool F[200001];

void buildStructure(){
    int i=1;
    segbr=0;
    for(int it : segmentIds){
        if(F[it]==0){tseg[i]=seg[it]; segbr++;}
        ++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.push_back(nextSegmentId);
}

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

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((int)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:31:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   31 | void buildStructure(){
      |                     ^
segments.cpp:67:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   67 | void handleQt1(int k){
      |                     ^
segments.cpp:78:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   78 | void handleQt2(int k){
      |                     ^
segments.cpp:84:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   84 | void handleQt3(int ti){
      |                      ^
segments.cpp:131:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  131 | int main()
      |          ^
segments.cpp: In function 'int main()':
segments.cpp:137:10: warning: unused variable 'l' [-Wunused-variable]
  137 | int i,qt,l,r,id,k,f=0,qbsz;
      |          ^
segments.cpp:137:12: warning: unused variable 'r' [-Wunused-variable]
  137 | int i,qt,l,r,id,k,f=0,qbsz;
      |            ^
segments.cpp:137:14: warning: unused variable 'id' [-Wunused-variable]
  137 | int i,qt,l,r,id,k,f=0,qbsz;
      |              ^~
segments.cpp:137:17: warning: unused variable 'k' [-Wunused-variable]
  137 | int i,qt,l,r,id,k,f=0,qbsz;
      |                 ^
segments.cpp:137:19: warning: unused variable 'f' [-Wunused-variable]
  137 | int i,qt,l,r,id,k,f=0,qbsz;
      |                   ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1846 ms 7400 KB Output is correct
2 Correct 1825 ms 7508 KB Output is correct
3 Correct 1830 ms 7372 KB Output is correct
4 Correct 1928 ms 7372 KB Output is correct
5 Correct 1978 ms 8392 KB Output is correct
6 Correct 1943 ms 8236 KB Output is correct
7 Correct 1812 ms 7436 KB Output is correct
8 Correct 1827 ms 7436 KB Output is correct
9 Correct 1809 ms 7380 KB Output is correct
10 Correct 989 ms 7288 KB Output is correct
11 Correct 1275 ms 7308 KB Output is correct
12 Correct 2071 ms 7932 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 6932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 2 ms 6492 KB Output isn't correct
4 Halted 0 ms 0 KB -