제출 #440711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440711		leaked	Segments (IZhO18_segments)	C++14	75 / 100	5069 ms	20132 KiB

segments

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC opimize(-O3)
#pragma GCC opimize(Ofast)
#pragma GCC opimize(unroll-loops)
#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int K=2800;
const int B=K;
const int N=2e5+2;
template <class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int l[N],r[N];
struct buben{
    deque<int>dq;
    ordered_set<pii>st;
    ordered_set<pii>st1;
}w[N/K+1];
ordered_set<pii>fal;
void ins(int i,int j){
    int b=i/K;
    w[b].dq.insert(w[b].dq.begin()+i%K,j);
    w[b].st.insert({r[j],j});w[b].st1.insert({r[j]-l[j]+1,j});
    while(sz(w[b].dq)>K){
        int v=w[b].dq.back();
        w[b+1].st.insert({r[v],v});w[b+1].st1.insert({r[v]-l[v]+1,v});
        w[b+1].dq.push_front(v);
        w[b].st.erase({r[v],v});w[b].st1.erase({r[v]-l[v]+1,v});
        w[b].dq.pop_back();
        b++;
    }
    fal.insert({l[j],j});
}
void del(int i,int j){
    int b=i/K;
    w[b].dq.erase(w[b].dq.begin()+(i%K),w[b].dq.begin()+(i%K)+1);
    w[b].st.erase({r[j],j});w[b].st1.erase({r[j]-l[j]+1,j});
    while(sz(w[b].dq)<K && sz(w[b+1].dq)){
        int v=w[b+1].dq.front();
        w[b+1].st.erase({r[v],v});w[b+1].st1.erase({r[v]-l[v]+1,v});
        w[b+1].dq.pop_front();
        w[b].st.insert({r[v],v});w[b].st1.insert({r[v]-l[v]+1,v});
        w[b].dq.push_back(v);
        b++;
    }
    fal.erase({l[j],j});
}
int fnd(int x){
    int id=fal.order_of_key(m_p(x,-1));
    return id;
}
int fnd(int x,int j){
    int id=fal.order_of_key(m_p(x,j));
    return id;
}
int get(int l1,int r1,int x){
    int ans=0;
    for(int i=l1/K;i<=r1/K;i++){
        int l2=i*B,r2=l2+B-1;
        if(l2>=l1 && r2<=r1){
            int lung=w[i].st1.order_of_key({x,-1});
            ans+=B-lung;
        }
        else{
            l2=max(l1,l2);r2=min(r1,r2);
            l2%=B;r2%=B;
            for(int j=l2;j<=r2;j++){
                int id=w[i].dq[j];
                ans+=((r[id]-l[id]+1)>=x);
            }
        }
    }
    return ans;
}
int get1(int l1,int r1,int x){
    int ans=0;
    for(int i=l1/K;i<=r1/K;i++){
        int l2=i*B,r2=l2+B-1;
        if(l2>=l1 && r2<=r1){
            ans+=B-w[i].st.order_of_key({x,-1});
        }
        else{
            l2=max(l1,l2);r2=min(r1,r2);
            l2%=B;r2%=B;
            for(int j=l2;j<=r2;j++){
                int id=w[i].dq[j];
                ans+=(r[id]>=x);
            }
        }
    }
    return ans;
}
int u=1;
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int q,t;
    cin>>q>>t;
    ///fuck this shit
    int lstans=0;
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int a,b;
            cin>>a>>b;
            a=(a^(lstans*t));
            b=(b^(lstans*t));
            if(a>b) swap(a,b);
            l[u]=a;r[u]=b;
            ins(fnd(l[u],u),u);
            u++;
        }
        else if(tp==2){
            int id;
            cin>>id;
            del(fnd(l[id],id),id);
        }
        else{
            int a,b,k;
            cin>>a>>b>>k;
            a=(a^(lstans*t));
            b=(b^(lstans*t));
            if(a>b) swap(a,b);
            if(b-a+1<k){
                lstans=0;
                cout<<0<<'\n';
                continue;
            }
            int lf=a,rt=b;
            int l1=fnd(lf),r1=fnd(rt-k+2)-1;
            int ans=get(l1,r1,k);
            ans+=get1(0,l1-1,k+lf-1);
            cout<<ans<<'\n';
            lstans=ans;
        }
    }
    return 0;
}
/*
5 1
1 1 2
1 3 5
3 2 3 1
2 1
3 0 3 1

*/

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp:4: warning: ignoring '#pragma GCC opimize' [-Wunknown-pragmas]
    4 | #pragma GCC opimize(-O3)
      | 
segments.cpp:5: warning: ignoring '#pragma GCC opimize' [-Wunknown-pragmas]
    5 | #pragma GCC opimize(Ofast)
      | 
segments.cpp:6: warning: ignoring '#pragma GCC opimize' [-Wunknown-pragmas]
    6 | #pragma GCC opimize(unroll-loops)
      |

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